הצדקת טקסט  


רמת קושי קשה
נשאל לעתים קרובות אמזון בעברית Coursera Google אכן לינקדין מיקרוסופט פינטרסט Snapchat
מחרוזת

הצהרת בעיה  

הבעיה "הצדקת טקסט" קובעת שאתה מקבל רשימות [] מהסוג מחרוזת בגודל 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. אתחל רשימות [] מהסוג מחרוזת בגודל 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 מחרוזת.