সি++-এ ওয়ার্ড জাস্টিফাই করা (সমান দৈর্ঘ্যের লাইনে রূপান্তর)

সমস্যা বিবরণ

ওয়ার্ডের একটি লিস্ট এবং প্রস্থ k দেওয়া আছে। টেক্সটকে এমনভাবে সাজাতে হবে যাতে প্রতিটি লাইনে ঠিক k ক্যারেক্টার থাকে এবং ফুলি জাস্টিফাইড হয়। এক্সট্রা স্পেস সমানভাবে বাঁটাতে হবে (বাম পাশে বেশি)। শেষ লাইন লেফট-জাস্টিফাইড হবে।

উদাহরণ: words = ["The","grumpy","wizards","make","toxic","brew","for","the","evil","queen","and","Jack"], k = 13

সমাধানের পদ্ধতি

1. লালচীভাবে (greedy) প্রতিটি লাইনে যতটা সম্ভব ওয়ার্ড প্যাক করুন।
2. লাইনের ওয়ার্ড সংখ্যা cnt, টোটাল ক্যারেক্টার width।
3. স্পেস ক্যালকুলেট করুন: space = (k - width) / (cnt - 1), extra = (k - width) % (cnt - 1)।
4. বাম থেকে ডানে স্পেস বাঁটান (extra হলে বামে ১ একস্ট্রা)।
5. শেষ লাইনে শুধু এক স্পেস দিয়ে লেফট-জাস্টিফাই করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> fullJustify(vector<string>& a, int b) {
        vector<string> result;
        for (int i = 0, j; 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, 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];
            }
            line += string(b - line.size(), ' ');
            result.push_back(line);
        }
        return result;
    }
};

int main() {
    vector<string> v = {"The","grumpy","wizards","make","toxic","brew","for","the","evil","queen","and","Jack"};
    Solution ob;
    for (auto& s : ob.fullJustify(v, 13)) cout << s << endl;
    return 0;
}

আউটপুট

The grumpy
wizards make
toxic brew
for the evil
queen and
Jack