โปรแกรมจัดเรียงข้อความให้กว้างเท่ากัน (Text Justification) ใน C++

ให้รายการคำ และความกว้าง k จัดข้อความให้แต่ละบรรทัดกว้างพอดี k ตัวอักษร จัดเต็ม (fully justified) ยกเว้นบรรทัดสุดท้ายจัดซ้าย

ช่องว่างกระจายเท่าๆ กัน ช่องซ้ายได้มากกว่าถ้าไม่หารลงตัว

ขั้นตอนการแก้ปัญหา

1. หาคำที่ใส่ได้ในบรรทัดนี้ (width + ความยาวคำ + ช่องว่าง <= k)
2. คำนวณ space = (k - total_width) / (จำนวนคำ - 1), extra = เศษ
3. สร้างบรรทัด: คำแรก + (space + extra--) ช่องว่าง + คำถัดไป...
4. บรรทัดสุดท้าย: จัดซ้าย ช่องว่าง 1 ช่อง ต่อท้ายด้วย space เหลือ

ตัวอย่างโค้ด C++

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

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        for (int i = 0, j; i < words.size(); i = j) {
            int width = 0;
            for (j = i; j < words.size() && width + words[j].size() + j - i <= maxWidth; j++)
                width += words[j].size();
            
            int space = 1, extra = 0;
            if (j - i != 1 && j != words.size()) {
                space = (maxWidth - width) / (j - i - 1);
                extra = (maxWidth - width) % (j - i - 1);
            }
            
            string line = words[i];
            for (int k = i+1; k < j; k++) {
                line += string(space, ' ');
                if (extra-- > 0) line += ' ';
                line += words[k];
            }
            line += string(maxWidth - 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, 16))
        cout << s << '\n';
    return 0;
}

อินพุต

["I","love","coding.","here","we","will","write","some","program"], 16

เอาต์พุต

["I love coding.  ","here we will    ","write some      ","program         "]