Мәтінді негіздеу


Күрделілік дәрежесі қиын
Жиі кіреді Amazon Coursera Google шынында LinkedIn Microsoft Pinterest Snapchat
String

Проблемалық мәлімдеме

«Мәтінді негіздеу» проблемасында сізге түрдің тізімі берілген [] көрсетілген жол n және an өлшемдері бүтін сан өлшемі. Мәтінді дәлелдеңіз, мәтіннің әрбір жолы таңбалардың көлемінен тұрады. Сызықтағы қажетті таңбалар санын аяқтау үшін таңба ретінде кеңістікті ('') пайдалануға болады.

Мәтінді негіздеу

мысал

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

Түсіндіру: Сөздер арасында бос орын қолдана алатындықтан, оларды жоғарыда келтірілген кескіннен көрініп тұрғандай дұрыс орналастырдық.

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

Мәтінді негіздеу алгоритмі

  1. S [] типті тізімді инициализациялаңыз жол n және an өлшемдері бүтін сан айнымалы өлшем.
  2. Тізімнен өтіп, әр сөзді / жолды тексеріңіз, егер ағымдағы сөздің ұзындығы берілген өлшемнен аз немесе оған тең болса, нәтижеге ағымдағы сөзді қосыңыз.
  3. Басқа жағдайда, егер ағымдағы жолдың / сөздің ұзындығы берілген өлшемнен үлкен болса, онда бос орындарды сызықтың қалған позицияларын аяқтаңыз.
  4. Егер сол жолдағы келесі сөздің және сол жолдағы алдыңғы сөздің ұзындығының қосындысы берілген өлшемнен аз немесе оған тең болса, нәтижеге ағымдағы сөзді қосып, қалған орындарды ақ түспен реттеңіз ғарыш.
  5. Басқа, егер сол жолдағы келесі сөздің ұзындығы мен сол жолдағы алдыңғы сөздің ұзындығының қосындысы берілген өлшемнен үлкен болса, нәтиженің келесі жолына ағымдағы сөзді қосып, қалған орындарды толтырыңыз. ақ сызықпен ағымдағы сызық.
  6. Алынған жолды басып шығарыңыз.

код

Мәтінді негіздеу бағдарламасы C ++

#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.

Мәтінді негіздеудің Java бағдарламасы

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.

Күрделілікті талдау

Уақыттың күрделілігі

O (n), мұндағы n - берілген s [] массивінің өлшемі. Біз а while цикл ішіндегі fullJustify, i және j айнымалыларының кез-келгені N-ден өтпейінше жұмыс істейді және бұл цикл аяқталуға сызықтық уақытты алады. Осылайша уақыттың күрделілігі сызықтық болып табылады.

Ғарыштың күрделілігі

O (n), өйткені біз n жолды сақтау үшін кеңістікті пайдаландық.