Տեքստի հիմնավորում


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են 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.

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ n է տրված տողի զանգվածի s [] չափը: Մենք վազում ենք ա իսկ հանգույց ներսում fullJustify, որը գործում է միայն այնքան ժամանակ, քանի դեռ i և j փոփոխականներից որևէ մեկը չի հատում N.- ն: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

O (n), քանի որ մենք տարածություն ենք օգտագործել n լարայինը պահելու համար: