Асосноккунии матн


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon Coursera Google Ҳақиқатан LinkedIn Microsoft ба дӯстат Snapchat
сатр

Изҳороти мушкилот

Масъалаи "Асосгузории матн" мегӯяд, ки ба шумо рӯйхати s [] навъи дода мешавад данд андозаи 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 [] мебошад. Мо иҷро карда истодаем дар ҳоле ки ҳалқа дохили fullJustify, ки танҳо то он даме ки яке аз тағирёбандаҳои i ва j аз N убур накунанд, кор мекунад ва ин ҳалқа барои хатми вақти хаттӣ мегирад. Ҳамин тавр мураккабии вақт хатӣ аст.

Мураккабии фазо

O (n), зеро мо фазоро барои нигоҳ доштани n сатр истифода кардем.