1. Tóm tắt đề bài

Cho một mảng

$S$ gồm các xâu và một độ dài

$maxWidth$. Bạn cần format lại các xâu này thoả mãn các điều kiện sau:

• Các xâu được chia ra thành nhiều dòng, mỗi dòng có độ dài đúng bằng
  $maxWidth$.
• Mỗi dòng phải chứa được nhiều từ nhất có thể.
• Phần space ở giữa các từ cần được phân bổ đều nhất có thể. Nếu space không thể phân bổ đều, phần space về phía bên trái sẽ nhiều hơn về phía bên phải.
• Ở dòng cuối, các từ sẽ được căn chỉnh theo lề trái, space giữa hai từ sẽ là 1.

Giới hạn

• $1\le |S|\le 300$.
• $1\le |S_i|\le 20$.
• $1\le maxWidth\le 100$.
• $1\le |S_i|\le maxWidth$

2. Tóm tắt lời giải

Chỉ cần làm đúng theo chỉ dẫn của đề bài.

Độ phức tạp dự tính:

$O(sum(S))$ với

$sum(S)$ là tổng độ dài tất cả các xâu

3. Lời giải chi tiết

Bài này chỉ cần làm theo đúng chỉ dẫn đề bài, với mỗi dòng thì tham lam cứ cho xâu vào dòng nếu còn đủ chỗ, nếu không thì sẽ cho xâu đó sang dòng mới.

Sau khi đã chọn dòng xong, ta sẽ format lại mỗi dòng sao cho đều. Lưu ý là dòng cuối sẽ được format khác so với các dòng còn lại.

Code tham khảo: https://leetcode.com/problems/text-justification/submissions/1030455091/

Độ phức tạp thuật toán

Thời gian:

$O(sum(S)$ với

$sum(S)$ là tổng độ dài tất cả các xâu

Bộ nhớ mở rộng:

$O(sum(S))$

4. Kết luận & Gợi ý mở rộng

Đây tuy là một bài hard nhưng code khá trực diện. Dù vậy vẫn cần phải chú ý đến các tiểu tiết bằng việc đọc kĩ đề bài nếu không sẽ rất dễ bị bug.