Mətnin əsaslandırılması LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Capital One Coursera eBay Facebook google Həqiqətən Karat LinkedIn microsoft Nvidia Kahin Pinterest Snapchat kvadrat Twilio Über
SimBaxılıb 35

Bu gün Mətn Əsaslandırması LeetCode Həllini müzakirə edəcəyik

Problem bəyanat

"Mətnin əsaslandırılması" problemi sizə bir növ siyahı [] verildiyini bildirir sim ölçüsü n və an tam ölçüsü. Mətni elə əsaslandırın ki, hər mətn sətri ölçülü simvoldan ibarət olsun. Bir sətirdə lazım olan simvolları tamamlamaq üçün boşluqdan ('') bir simvol kimi istifadə edə bilərsiniz.

Mətnin əsaslandırılması LeetCode HəlliPin

misal

s = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."}
size = 12
TutorialCup
is  the best
portal   for
programming.

Izahat: Sözlər arasındakı boşluqlardan istifadə edə bildiyimiz üçün yuxarıda yerləşdirilmiş şəkildə göründüyü kimi onları düzgün bir şəkildə yerləşdirdik.

s = {"This", "article", "is", "contributed", "by", "Akshita", "Jain"}
size = 13
This  article
is
contributed
by    Akshita
Jain

Mətnin əsaslandırılması üçün alqoritm LeetCode Həlli

  1. Bir növ s [] növünü başlatın sim ölçüsü n və an tam dəyişən ölçüsü.
  2. Siyahıdan keçin və cari sözün uzunluğu verilmiş ölçüdən az və ya bərabərdirsə, hər bir söz / sətri yoxlayın, nəticəyə cari sözü əlavə edin.
  3. Başqa bir cari sətrin / sözün uzunluğu verilən ölçüdən böyükdürsə, sətrin qalan mövqelərini tamamlamaq üçün ağ boşluqlardan istifadə edin.
  4. Eyni sətirdə növbəti sözün uzunluğunun və eyni sətirdə əvvəlki sözün uzunluğunun cəmi verilmiş ölçüdən az və ya bərabərdirsə, cari sözü nəticəyə əlavə edin və qalan yerləri ağ ilə düzəldin. yer.
  5. Başqa sözlə eyni sətirdə növbəti sözün uzunluğunun və eyni sətirdə əvvəlki sözün uzunluğunun cəmi verilmiş ölçüdən böyükdürsə, nəticənin növbəti sətirində cari sözü əlavə edin və qalan yerləri doldurun. ağ boşluq ilə cari xətt.
  6. Yaranan sətri çap edin.

Kodu

C ++ Mətnin əsaslandırılması proqramı

#include "bits/stdc++.h" 
using namespace std; 
  
string getSpaces(int n){
    string s = "";
    for(int i=0; i<n;i++) s += " ";
    return s; 
}

string getLine(vector<string>& words, int start, int end, int letterCount, int maxWidth){
    string res = words[start];
    int spaces = maxWidth - letterCount;
    
    if(start == end){ 
        res += getSpaces(spaces);
        return res;
    }
    
    int numOfSpace = spaces/(end-start);
    int extraOne = spaces%(end-start);
    string space0 = getSpaces(numOfSpace);
    string space1 = space0 + " "; 
    
    for(int i= 0; i< end-start; i++){
        res  = res + (i < extraOne? space1: space0) + words[start + 1 + i];
    }
    return res; 
}

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    int N = words.size(); 
    int i = 0, j = 0;
    int counter = 0; 
    vector<string> res; 
    
    while(i<N && j<N){
        int len = words[j].length(); 
        counter += len;
        
        if(counter + j - i > maxWidth){
            counter -= len; 
            res.push_back(getLine(words, i, j-1, counter, maxWidth));
            i = j; 
            counter = 0; 
        }
        
        else{
            j++;
        }
    }
    
    if(counter){
        string last = words[i];
        
        for(int x=i+1; x < j; x++){ 
            last = last + " " + words[x];
        }
        
        last = last + getSpaces(maxWidth - last.size());
        res.push_back(last);
    }

    return res; 
}

int main(){
    vector<string> s = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."};
    int size = 12;
    
    vector<string> lines = fullJustify(s, size); 
    
    for(auto x: lines)
        cout << x << endl;
    
    return 0; 
}
TutorialCup 
is  the best
portal   for
programming.

Mətnin əsaslandırılması üçün Java proqramı

import java.util.*;

class TextJustification{
    
    static List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int size = words.length;
        int index = 0;
        
        while (index < size){
            int totalChars = words[index].length();
            int lastIndex = index + 1;
            int gaps = 0;
            
            while (lastIndex < size){
                if (totalChars + 1 + words[lastIndex].length() > maxWidth){
                    break;
                }
                totalChars += 1 + words[lastIndex++].length();
                gaps++;
            }
            
            StringBuilder sb = new StringBuilder();
            
            if (lastIndex == size || gaps == 0){
                for (int i = index; i < lastIndex; ++i){
                    sb.append(words[i]).append(' ');
                }
                sb.deleteCharAt(sb.length() - 1);
                while (sb.length() < maxWidth){
                    sb.append(' ');
                }
            } 
            
            else {
                int spaces = (maxWidth - totalChars) / gaps;
                int restSpaces = (maxWidth - totalChars) % gaps;
                for (int i = index; i < lastIndex - 1; ++i){
                    sb.append(words[i]).append(' ');
                    for (int j = 0; j < spaces + (i - index < restSpaces ? 1 : 0); ++j){
                        sb.append(' ');
                    }
                }
                sb.append(words[lastIndex - 1]);
            }
            
            res.add(sb.toString());
            index = lastIndex;
        }
        return res;
    }
  
  public static void main (String[] args){
      
      String[] words = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."};
      int size = 12;
      
      List<String> res = new ArrayList<String>();
      res = fullJustify(words, size);
      ListIterator<String> lItr = res.listIterator();
      
      while (lItr.hasNext()){
          System.out.println(lItr.next());
      }
  }
}
  
TutorialCup 
is  the best
portal   for
programming.

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n), burada n - verilən sətir massivinin ölçüsü []. Biz çalışırıq döngə zamanı içində yalnız i və j dəyişənlərindən biri N-dən keçməyincə işləyən fullJustify və bu döngənin sona çatması üçün xətti vaxt tələb olunur. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (n), çünki n simli saxlamaq üçün yer istifadə etdik.

Translate »
1