පෙළ සාධාරණීකරණය


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇමේසන් Coursera ගූගල් ඇත්ත වශයෙන්ම LinkedIn මයික්රොසොෆ්ට් Pinterest Snapchat
String

ගැටළු ප්රකාශය

“පෙළ සාධාරණීකරණය” යන ගැටලුවේ සඳහන් වන්නේ ඔබට වර්ගීකරණ ලැයිස්තුවක් ලබා දී ඇති බවයි පේළියකි n ප්‍රමාණය සහ a නිඛිල ප්‍රමාණය. සෑම පෙළක්ම විශාල ප්‍රමාණයේ අක්ෂර ගණනකින් සමන්විත වන පරිදි පෙළ සාධාරණීකරණය කරන්න. පේළියක අවශ්‍ය අක්‍ෂර ගණන සම්පූර්ණ කිරීම සඳහා ඔබට අවකාශය ('') අක්ෂරයක් ලෙස භාවිතා කළ හැකිය.

පෙළ සාධාරණීකරණය

උදාහරණයක්

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 ප්‍රමාණය සහ a නිඛිල විචල්ය ප්රමාණය.
  2. ලැයිස්තුව හරහා ගමන් කර එක් එක් වචනය / නූල සඳහා වත්මන් වචනයේ දිග ලබා දී ඇති ප්‍රමාණයට වඩා අඩු හෝ සමාන දැයි පරීක්ෂා කරන්න, ප්‍රති word ලයට වත්මන් වචනය එක් කරන්න.
  3. වෙනත් නූල් / වචනයේ දිග ලබා දී ඇති ප්‍රමාණයට වඩා වැඩි නම්, රේඛාවේ ඉතිරි ස්ථාන සම්පූර්ණ කිරීම සඳහා සුදු අවකාශයන් භාවිතා කරන්න.
  4. එකම පේළියේ ඊළඟ වචනයේ දිග හා එකම පේළියේ පෙර වචනයේ දිග ලබා දී ඇති ප්‍රමාණයට වඩා අඩු හෝ සමාන නම්, ප්‍රති word ලයට වත්මන් වචනය එකතු කර ඉතිරි ස්ථාන සුදු පැහැයෙන් සකසන්න අවකාශය.
  5. වෙනත් පේළියක එකම පේළියේ දිග හා එකම පේළියේ පෙර වචනයේ දිග ලබා දී ඇති ප්‍රමාණයට වඩා වැඩි නම්, ප්‍රති word ලයේ ඊළඟ පේළියේ වත්මන් වචනය එකතු කර ඉතිරි ස්ථාන පුරවන්න වත්මන් රේඛාව සුදු අවකාශය සමඟ.
  6. එහි ප්‍රති string ලය වන නූල මුද්‍රණය කරන්න.

කේතය

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 ඉක්මවා නොයන තෙක් පමණක් ක්‍රියාත්මක වන fullJustify තුළ මෙම ලූපය අවසන් වීමට රේඛීය කාලයක් ගතවේ. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

O (n) නිසා අපි n string ගබඩා කිරීමට ඉඩ භාවිතා කළෙමු.