Căn chỉnh văn bản (Text Justification) trong C++

Cho mảng từ và độ rộng maxWidth. Định dạng văn bản sao cho mỗi dòng đúng maxWidth ký tự và căn đều hai bên. Đưa từ vào tham lam (nhiều nhất có thể). Phân bổ khoảng trắng đều; nếu không chia hết, bên trái nhận nhiều hơn. Dòng cuối cùng căn trái, không thêm khoảng trắng giữa các từ.

Giải thuật

• Tạo mảng result.
• Duyệt i từ 0 đến cuối mảng, cập nhật i = j:
  • width = 0.
  • Tìm j lớn nhất sao cho width + độ dài từ[j] + (j - i) <= maxWidth.
  • space = 1, extra = 0.
  • Nếu không phải từ đơn và không phải dòng cuối: space = (maxWidth - width) / (j - i - 1), extra = (maxWidth - width) % (j - i - 1).
  • Xây dựng dòng: bắt đầu từ từ[i], với mỗi từ tiếp theo thêm space khoảng trắng, nếu extra > 0 thêm 1 khoảng trắng, giảm extra.
  • Đệm khoảng trắng cuối để đủ maxWidth.
  • Thêm dòng vào result.

Ví dụ minh họa (C++)

#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;
}

Đầu vào

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

Đầu ra

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