စာသားĠustifikazzjoni


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ Coursera Google တကယ်ပါပဲ LinkedIn တို့ Microsoft က Pinterest Snapchat
ကြိုး

ပြProbleနာဖော်ပြချက်

ပြTextနာက“ စာသားမျှတမှု” ကသင့်ကိုအမျိုးအစား [စာရင်း] ပေးတယ်လို့ဖော်ပြထားတယ် ကြိုး အရွယ်အစား n နှင့်တစ် ဦး ၏ ကိန်း အရွယ်အစား။ စာသား၏လိုင်းတိုင်းတွင်စာလုံးအရေအတွက်ပါ ၀ င်စေရန်စာသားကိုဖြောင့်မတ်ပါစေ။ လိုအပ်သောအက္ခရာအရေအတွက်ကိုမျဉ်းကြောင်းတစ်ခုပြီးမြောက်ရန်အက္ခရာတစ်ခုအဖြစ် space (') ကိုသုံးနိုင်သည်။

စာသားĠustifikazzjoni

နမူနာ

s = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."}
size = 12
TutorialCup
is  the best
portal   for
programming.

ရှင်းလင်းချက်ဖြေ - စကားလုံးတွေကြားမှာအကွာအဝေးတွေကိုသုံးနိုင်တဲ့အတွက်အပေါ်က embedded ပုံမှာတွေ့ရသလိုပဲသူတို့ကိုစနစ်တကျနေရာချလိုက်တယ်။

s = {"This", "article", "is", "contributed", "by", "Akshita", "Jain"}
size = 13
This  article
is
contributed
by    Akshita
Jain

စာသားĠustifikazzjoniများအတွက် Algorithm

  1. စာရင်းတစ်ခု [] အမျိုးအစားအမျိုးအစားကိုအစပြုပါ ကြိုး အရွယ်အစား n နှင့်တစ် ဦး ၏ ကိန်း variable အရွယ်အစား။
  2. စာရင်းအား ဖြတ်၍ ဖြတ်သန်း။ လက်ရှိစကားလုံး၏အရှည်သည်ပေးထားသောအရွယ်အစားနှင့်ညီသည်ဆိုပါကစကားလုံးတစ်လုံးစီကိုစစ်ဆေးပါ။ ရလဒ်ကိုလက်ရှိစကားလုံးကိုထည့်ပါ။
  3. အကယ်၍ လက်ရှိ string / word အရှည်သည်ပေးထားသောအရွယ်အစားထက်ကြီးပါကအဖြူရောင်နေရာများကို သုံး၍ မျဉ်း၏ကျန်နေရာများကိုဖြည့်စွက်ပါ။
  4. လာမည့်စကားလုံး၏တူညီသောမျဉ်းကြောင်းနှင့်အတူတူပင်လိုင်းတစ်ခုတည်းရှိယခင်စကားလုံး၏အရှည်သည်စုစုပေါင်းပမာဏနှင့်ညီမျှလျှင်၊ လက်ရှိစကားလုံးကိုရလဒ်သို့ဖြည့်ပြီးကျန်ရှိသောနေရာများကိုအဖြူရောင်ဖြင့်ချိန်ညှိပါ။ အာကာသ။
  5. နောက်တစ်ခုမှာမျဉ်းကြောင်းတစ်ခုတည်းရှိလာမည့်စကားလုံး၏အရှည်နှင့်ယခင်စကားလုံး၏အရှည်သည်ပေးထားသောအရွယ်အစားထက်ကြီးပါက၊ လက်ရှိစကားလုံးကိုနောက်လိုင်းတွင်ထည့်ပြီးကျန်ရှိသောနေရာများကိုဖြည့်ပါ။ အဖြူအာကာသနှင့်အတူလက်ရှိလိုင်း။
  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.

စာသားမျှတမှု၏ 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.

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (n) n သည်ပေးထားသော string array ၏အရွယ်အစားဖြစ်သည်။ ငါတို့ပြေးနေတယ် နေစဉ်ကွင်းဆက် fullJustify အတွင်းမှာပဲ i နဲ့ j variable တစ်ခုခုက N. ကိုမဖြတ်နိုင်ဘူးဆိုရင်အဲ့ဒီ loop ကအဆုံးသတ်ဖို့ linear အချိန်လိုအပ်တယ်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို ()) ကျွန်ုပ်တို့သည် string string ကိုသိုလှောင်ရန်နေရာသုံးသောကြောင့်ဖြစ်သည်။