पाठ औचित्य


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना Coursera गूगल वास्तव में लिंक्डइन माइक्रोसॉफ्ट Pinterest Snapchat
तार

समस्या का विवरण

समस्या "पाठ औचित्य" बताता है कि आपको एक सूची दी गई है [] प्रकार की स्ट्रिंग आकार एन और ए पूर्णांक आकार। पाठ को ऐसे लिखें कि पाठ की प्रत्येक पंक्ति में वर्णों की संख्या शामिल हो। आप एक पंक्ति में वर्णों की आवश्यक संख्या को पूरा करने के लिए एक चरित्र के रूप में स्थान ('') का उपयोग कर सकते हैं।

पाठ औचित्य

उदाहरण

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. प्रकार की सूची [] को प्रारंभ करें स्ट्रिंग आकार एन और ए पूर्णांक परिवर्तनशील आकार।
  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.

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

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 स्ट्रिंग को स्टोर करने के लिए स्पेस का उपयोग किया है।