Mô tả bài toán
Cho danh sách từ và độ rộng k. Sắp xếp từ vào các dòng độ dài chính xác k, căn đều hai bên (fully justified). Dòng cuối cùng căn trái. Khoảng trắng phân bố đều, dư thừa phân bố bên trái.
Ví dụ: words = ["The","grumpy","wizards","make","toxic","brew","for","the","evil","queen","and","Jack"], k=13.
Giải thuật
- Duyệt words, gom tối đa từ cho mỗi dòng sao cho tổng độ dài từ + khoảng trắng tối thiểu ≤ k.
- Tính số khoảng trắng cần chèn: space = (k - total_word_len) / (số từ - 1), extra = dư.
- Xây dựng dòng: từ đầu tiên, sau mỗi từ chèn space khoảng trắng, nếu extra>0 thêm 1 khoảng trắng và giảm extra.
- Dòng cuối: nối từ bằng 1 khoảng trắng, đệm khoảng trắng cuối để đủ k.
Ví dụ minh họa (C++)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> result;
int i = 0, n = words.size();
while (i < n) {
int j = i, lineLen = 0;
while (j < n && lineLen + words[j].size() + (j - i) <= maxWidth) {
lineLen += words[j].size();
j++;
}
int space = 1, extra = 0;
if (j - i != 1 && j != n) {
space = (maxWidth - lineLen) / (j - i - 1);
extra = (maxWidth - lineLen) % (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);
i = j;
}
return result;
}
};
int main() {
vector<string> v = {"The","grumpy","wizards","make","toxic","brew","for","the","evil","queen","and","Jack"};
Solution ob;
for (auto& line : ob.fullJustify(v, 13)) cout << line << endl;
return 0;
}
Đầu ra mẫu
The grumpy wizards make toxic brew for the evil queen and Jack