मान लीजिए हमारे पास शब्दों का एक ऐरे और एक चौड़ाई maxWidth है, हमें टेक्स्ट को इस तरह फॉर्मेट करना है कि प्रत्येक लाइन में ठीक maxWidth कैरेक्टर्स हों और यह पूरी तरह से जस्टिफाइड हो। हमें शब्दों को लालची दृष्टिकोण से पैक करना चाहिए; यानी प्रत्येक लाइन में जितने संभव हो उतने शब्द पैक करें। हम आवश्यकता पड़ने पर अतिरिक्त स्पेस ' ' पैड करेंगे ताकि प्रत्येक लाइन में ठीक maxWidth कैरेक्टर्स हों।
यहां शब्दों के बीच अतिरिक्त स्पेस को यथासंभव समान रूप से वितरित किया जाना चाहिए। यदि एक लाइन पर स्पेस की संख्या शब्दों के बीच समान रूप से विभाजित नहीं होती है, तो बाएं स्लॉट्स को दाएं स्लॉट्स की तुलना में अधिक स्पेस दिए जाएंगे। टेक्स्ट की अंतिम लाइन के लिए, यह बाएं जस्टिफाइड होनी चाहिए और शब्दों के बीच कोई अतिरिक्त स्पेस नहीं डाला जाना चाहिए।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- result नामक एक ऐरे बनाएं
- i को 0 से a के आकार तक लूप चलाएं, i को j से अपडेट करें:
- width := 0
- j को i से a के आकार तक लूप चलाएं जब तक width + a[j] का आकार + j - i <= b:
- width := width + a[j] का आकार
- space := 1, extra := 0
- यदि j - i != 1 और j != a का आकार, तो:
- space := (b - width) / (j - i - 1)
- extra := (b - width) % (j - i - 1)
- line := a[i]
- k को i+1 से j तक लूप चलाएं:
- space संख्या के खाली स्पेस को line के साथ जोड़ें
- यदि extra > 0, तो line के साथ एक स्पेस जोड़ें
- extra को 1 घटाएं
- line := a[k] को line के साथ जोड़ें
- x := line का आकार
- line := (b - x) संख्या के स्पेस को line के साथ जोड़ें
- line को result में डालें
- result वापस करें
उदाहरण (C++ कोड)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
void print_vector(vector<vector<auto>> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << "[";
for(int j = 0; j < v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> fullJustify(vector<string> &a, int b) {
vector<string> result;
int i, j;
for(i = 0; i < a.size(); i = j){
int width = 0;
for(j = i; j < a.size() && width + a[j].size() + j - i <= b; j++){
width += a[j].size();
}
int space = 1;
int extra = 0;
if(j - i != 1 && j != a.size()){
space = (b - width) / (j - i - 1);
extra = (b - width) % (j - i - 1);
}
string line(a[i]);
for(int k = i + 1; k < j; k++){
line += string(space, ' ');
if(extra-- > 0){
line += " ";
}
line += a[k];
}
int x = line.size();
line += string(b - x, ' ');
result.push_back(line);
}
return result;
}
};
int main(){
vector<string> v = {"I", "love", "coding.", "here", "we", "will", "write", "some", "program"};
Solution ob;
print_vector(ob.fullJustify(v, 16));
}
इनपुट
["I", "love", "coding.", "here", "we", "will", "write", "some", "program"] 16
आउटपुट
[I love coding., here we will, write some, program , ]
