ধরুন আমাদের কাছে শব্দের একটি অ্যারে এবং একটি প্রস্থ maxWidth আছে। আমাদের কাজ হল টেক্সট ফরম্যাট করা যাতে প্রতিটি লাইনে ঠিক maxWidth সংখ্যক অক্ষর থাকে এবং এটি সম্পূর্ণ জাস্টিফাইড (justified) হয়। আমরা লালচী পদ্ধতিতে (greedy approach) শব্দগুলো প্যাক করব - অর্থাৎ প্রতিটি লাইনে যতটা সম্ভব শব্দ রাখব। প্রয়োজনে অতিরিক্ত স্পেস ' ' দিয়ে প্যাড করব যাতে প্রতিটি লাইনে ঠিক maxWidth অক্ষর থাকে।
এখানে শব্দগুলোর মাঝপথের অতিরিক্ত স্পেসগুলো যতটা সম্ভব সমানভাবে বণ্টন করা হবে। যদি একটি লাইনের স্পেসগুলো সমানভাবে ভাগ না যায়, তবে বাম দিকের খালি জায়গাগুলো ডান দিকের চেয়ে বেশি স্পেস পাবে। টেক্সটের চূড়ান্ত লাইনটি বাম জাস্টিফাইড (left justified) হবে এবং শব্দগুলোর মাঝপথে কোনো অতিরিক্ত স্পেস যোগ করা হবে না।
সমাধানের ধাপসমূহ:
result নামে একটি অ্যারে তৈরি করুন
i = 0 থেকে a.size() পর্যন্ত, i = j দিয়ে আপডেট করুন
width := 0
j = i থেকে a.size() পর্যন্ত এবং width + a[j].size() + j - i <= b পর্যন্ত: width += a[j].size()
space := 1, extra := 0
যদি j - i != 1 এবং j != a.size() হয়, তবে space = (b - width) / (j - i - 1), extra = (b - width) % (j - i - 1)
line := a[i]
k = i+1 থেকে j পর্যন্ত: line-এ space সংখ্যক স্পেস যোগ করুন, যদি extra > 0 হয় তবে একটি স্পেস যোগ করুন, extra--, line-এ a[k] যোগ করুন
x := line.size(), line-এ (b - x) সংখ্যক স্পেস যোগ করুন
result-এ line যোগ করুন
result রিটার্ন করুন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v) {
cout << "[";
for(int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
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));
return 0;
}
ইনপুট
["I", "love", "coding.", "here", "we", "will", "write", "some", "program"] 16
আউটপুট
[I love coding., here we will, write some, program , ]
