68. Text Justification

Problem

Bài toán yêu cầu chia một mảng các từ (words) thành các dòng, mỗi dòng có độ dài đúng bằng maxWidth, căn lề hai bên (full justify). Các dòng (trừ dòng cuối) phải phân phối khoảng trắng giữa các từ càng đều càng tốt, nếu không chia đều được thì ưu tiên thêm khoảng trắng vào các khe bên trái hơn.

Dòng cuối cùng chỉ căn lề trái (left-justify)

Approach

Duyệt qua từng từ, gom các từ vào một dòng sao cho tổng độ dài các từ và số khoảng trắng tối thiểu giữa chúng không vượt quá maxWidth

Khi không thể thêm từ tiếp theo vào dòng hiện tại, tiến hành căn lề cho dòng đó”

Nếu là dòng cuối hoặc chỉ có 1 từ: Nối các từ bằng một khoảng trắng, thêm khoảng trắng vào cuối dòng cho đủ maxWidth

Nếu không phải dòng cuối: Tính tổng số khoảng trắng cần chèn, chia đều vào các khe giữa các từ, khe bên trái nhận thêm nếu không chia hết

Time and space complexity

TC: O(n), với n là số lượng từ trong mảng words

SC: O(n * maxWidth), với n là số từ và maxWidth là độ dài tối đa của mỗi dòng

Solution

typescripttypescript

1function fullJustify(words: string[], maxWidth: number): string[] {
2    const res: string[] = [];
3    let i = 0;
4    const n = words.length;
5
6    while (i < n) {
7        let line_words: string[] = [words[i]];
8        let line_length = words[i].length;
9        i++;
10
11        while (i < n && line_length + 1 + words[i].length <= maxWidth) {
12            line_words.push(words[i]);
13            line_length += 1 + words[i].length;
14            i++
15        }
16
17        if (i === n || line_words.length === 1) {
18            const line = line_words.join(" ");
19            res.push(line + ' '.repeat(maxWidth - line.length));
20            continue;
21        }
22
23        const total_spaces = maxWidth - (line_length - (line_words.length - 1));
24        const space_per_gap = Math.floor(total_spaces / (line_words.length - 1));
25        const extra_spaces = total_spaces % (line_words.length - 1);
26
27        let line = '';
28        for (let j = 0; j < line_words.length - 1; j++) {
29            line += line_words[j];
30            line += ' '.repeat(space_per_gap + (j < extra_spaces ? 1 : 0));
31        }
32        line += line_words[line_words.length - 1];
33        res.push(line);
34    }
35
36    return res;
37};

💡

space_per_gap là gì?

Đây là số khoảng trắng tối thiểu cần chèn vào mỗi khoảng trống giữa các từ để dòng đạt gần tới độ dài maxWidth

Được tính bằng phép chia lấy phần nguyên

space_per_gap = Math.floor(total_spaces / (line_words.length - 1))

Vậy tại sao cần extra_spaces ?

Khi chia tổng số khoảng trắng (total_spaces ) cho số khoảng trống giữa các từ (line_words.length - 1 ), thường sẽ dư ra một số khoảng trắng (không chia hết)

extra_spaces chính là phần dư này:

extra_spaces = total_spaces % (line_words.length - 1)

Để căn lề đều, ta cần phần bổ đều phần dư này cho các khoảng trống đầu tiên trong dòng

Tại sao phải trừ line_words.length - 1?

line_len đã bao gồm cả dấu cách tối thiểu giữa các từ (mỗi từ thêm sau sẽ cộng thêm 1 dấu cách)

Tuy nhiên, khi căn lề đều, tất cả các dấu cách cũ sẽ bị thay thế bởi số dấu cách mới (nhiều hơn hoặc ít hơn 1)

Do đó, phải loại bỏ dấu cách tối thiểu này khỏi tổng độ dài hiện tại (line_len ), để chỉ còn tổng độ dài các ký tự của các từ

Vì vậy:

line_len - (line_words.length - 1) = tổng số ký tự của các từ (không tính dấu cách)

maxWidth - (line_len - (line_words.length - 1)) = tổng số khoảng trắng cần chèn vào dòng để đủ độ dài maxWidth

💡

Biến extra_spaces logic xử lý là gì?

Biến có vai trò xác định số khoảng trắng dư khi phân phối đều các khoảng trắng giữa các từ trong một dòng (trừ dòng cuối hoặc dòng chỉ có 1 từ)

Cụ thể:

Khi căn lề đều (full justify), tổn số khoảng trắng cần chèn giữa các từ là total_spaces

Số khe giữa các từ là line_words.length - 1;

Khi chia đều, mỗi khe nhận Math.floor(total_spaces / (line_words.length -1 )) khoảng trắng

Tuy nhiên, nếu total_spaces không chia hết cho số khe, sẽ còn dư ra extra_spaces khoảng trắng

Quy tắc là các khoảng trắng dư này được ưu tiên chèn vào các khe bên trái trước (tức là các khe đầu tiên từ trái sang phải sẽ nhận thêm 1 khoảng trắng cho đến khi hết extra_spaces)

Loading content...

1function fullJustify(words: string[], maxWidth: number): string[] { 2 const res: string[] = []; 3 let i = 0; 4 const n = words.length; 5 6 while (i < n) { 7 let line_words: string[] = [words[i]]; 8 let line_length = words[i].length; 9 i++; 10 11 while (i < n && line_length + 1 + words[i].length <= maxWidth) { 12 line_words.push(words[i]); 13 line_length += 1 + words[i].length; 14 i++ 15 } 16 17 if (i === n || line_words.length === 1) { 18 const line = line_words.join(" "); 19 res.push(line + ' '.repeat(maxWidth - line.length)); 20 continue; 21 } 22 23 const total_spaces = maxWidth - (line_length - (line_words.length - 1)); 24 const space_per_gap = Math.floor(total_spaces / (line_words.length - 1)); 25 const extra_spaces = total_spaces % (line_words.length - 1); 26 27 let line = ''; 28 for (let j = 0; j < line_words.length - 1; j++) { 29 line += line_words[j]; 30 line += ' '.repeat(space_per_gap + (j < extra_spaces ? 1 : 0)); 31 } 32 line += line_words[line_words.length - 1]; 33 res.push(line); 34 } 35 36 return res; 37};

68. Text Justification

Related Posts

Related Posts

68. Text Justification

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists