ટેક્સ્ટ જસ્ટિફિકેશન


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન Coursera Google ખરેખર LinkedIn માઈક્રોસોફ્ટ 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. પરિણામી શબ્દમાળા છાપો.

કોડ

સી ++ ટેક્સ્ટ જસ્ટિફિકેશનનો પ્રોગ્રામ

#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 એ આપેલ શબ્દમાળાના એરે [s] નું કદ છે. અમે ચલાવી રહ્યા છીએ એ જ્યારે લૂપ ફુલજસ્ટિફાઇ અંદર જે ફક્ત i અને j વેરીએબલ બંનેમાંથી N ના પાર ન થાય ત્યાં સુધી ચાલે છે અને આ લૂપ સમાપ્ત થવા માટે રેખીય સમય લે છે. આમ સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (એન) કારણ કે અમે n શબ્દમાળા સ્ટોર કરવા માટે જગ્યાનો ઉપયોગ કર્યો છે.