पाठ औचित्य


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन Coursera गुगल वास्तवमा LinkedIn माइक्रोसफ्ट Pinterest Snapchat
घागो

समस्या वक्तव्य

समस्या "पाठ औचित्य" बताउँछ कि तपाईंलाई सूची [s] प्रकारको दिइएको छ string आकार एन र एक को पूर्णांक आकार पाठलाई जस्टिफाई गर्नुहोस् कि पाठको प्रत्येक लाइनमा वर्ण संख्याको आकार हुन्छ। तपाईले स्पेस ('') लाई रेखामा आवश्यक वर्णहरूको संख्या पूर्ण गर्न क्यारेक्टरको रूपमा प्रयोग गर्न सक्नुहुनेछ।

पाठ औचित्य

उदाहरणका

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] सुरू गर्नुहोस् string आकार एन र एक को पूर्णांक चर आकार।
  2. सूचीबाट पार गर्नुहोस् र प्रत्येक शब्द / स्ट्रि stringको लागि जाँच गर्नुहोस् यदि हालको शब्दको लम्बाई दिइएको आकार भन्दा कम वा बराबर छ भने, परिणाममा हालको शब्द थप्नुहोस्।
  3. अन्यथा यदि हालको स्ट्रि / / शब्दको लम्बाई दिइएको आकार भन्दा ठूलो छ भने, सेतो रिक्त स्थान को उपयोग गरी लाइनको बाँकी पोजीशन पूरा गर्न।
  4. यदि उहि प line्क्तिमा अर्को शब्दको लम्बाई र समान रेखामा अघिल्लो शब्दको लम्बाइको योग दिइएको आकार भन्दा कम वा बराबर छ भने, हालको शब्दलाई परिणाममा थप्नुहोस् र बाँकी ठाउँहरूलाई सेतोसँग मिलाउनुहोस्। ठाउँ।
  5. अन्यथा यदि उहि प line्क्तिमा अर्को शब्दको लम्बाई र उही रेखामा अघिल्लो शब्दको लम्बाइ दिइएको आकार भन्दा ठूलो भए, परिणामको अर्को रेखामा हालको शब्द थप्नुहोस् र बाँकी ठाउँहरू भर्नुहोस्। सेतो खाली स्थानको साथ वर्तमान रेखा।
  6. नतिजाको स्ट्रि Print प्रिन्ट गर्नुहोस्।

कोड

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.

जावा पाठ पाठ औचित्य को कार्यक्रम

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 दिइएको स्ट्रिंग एर्रेको आकार हो []। हामी एक चलिरहेका छौं जबकि लुप पूर्ण जस्टिफाई भित्र जुन i र j भेरिएबल मध्ये कुनै एक लाई N पार गर्न नसक्दा मात्र चल्दछ। र यो लूप अन्त्य हुन लाईन समय लिन्छ। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (n) किनभने हामीले n स्ट्रि store भण्डार गर्न खाली ठाउँको प्रयोग गर्‍यौं।