Cover image for Interview Classic 150 Questions P68 Text Justification

Interview Classic 150 Questions P68 Text Justification

(Updated: )
algorithm
, , ,
Timeline

timeline

2025-11-10

init

array, string

Title:

P68 Text Justification

https://leetcode.cn/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150

Direct simulation, calculate how many words each line can hold, and how many spaces after each word.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <vector>
#include <string>
using std::vector;
using std::string;

class Solution {
    public:
	vector<string> fullJustify(vector<string> &words, int maxWidth)
	{
		int i, j, n = words.size();
		int start = 0;
		int curr_words_size;
		int blank_space_num;
		int word_space;
		int line_word_num;
		int extra_space;
		vector<string> res;

		while (start < n) {
			// Calculate how many words the current line can hold, starting from start
			curr_words_size = 0;
			for (i = 0; start + i < n; i++) {
				if (curr_words_size + words[start + i].size() + i <= maxWidth) { //Add spaces
					curr_words_size += words[start + i].size();
				} else {
					break;
				}
			}
			// start .. start+i total i words
			line_word_num = i;
			// Number of spaces
			blank_space_num = maxWidth - curr_words_size;

			string curr;
			if (start + line_word_num >= n) { //Last line
				for (i = 0; i < line_word_num; i++) {
					curr += words[start + i];
					curr += ' ';
				}
				if (curr.size() != 0) { //Remove spaces after the last word
					curr.pop_back();
				}
				// How many spaces are left to add to the end
				for (i = 0; i < blank_space_num - line_word_num + 1; i++) {
					curr += ' ';
				}
				res.push_back(curr);
				break;
			}

			if (line_word_num == 0) {
				break;
			} else if (line_word_num == 1) {
				//Only one word
				curr += words[start];
				for (i = 0; i < blank_space_num; i++) {
					curr += ' ';
				}
			} else if (line_word_num > 1) {
				// The last letter does not need a space, the preceding letters need at least word_space spaces
				word_space = blank_space_num / (line_word_num - 1);
				extra_space = blank_space_num % (line_word_num - 1);
				if (extra_space == 0) {
					for (i = 0; i < line_word_num - 1; i++) {
						curr += words[start + i];
						for (j = 0; j < word_space; j++) {
							curr += ' ';
						}
					}
				} else {
					for (i = 0; i < line_word_num - 1; i++) {
						curr += words[start + i];
						if (i < extra_space) {
							curr += ' ';
						}
						for (j = 0; j < word_space; j++) {
							curr += ' ';
						}
					}
				}
				//The last word
				curr += words[start + i];
			}

			res.push_back(curr);

			start = start + line_word_num;
		}

		return res;
	}
};

#include <stdio.h>
int main()
{
	vector<string> words = { "Science", "is", "what",	"we",	"understand", "well",
				 "enough",  "to", "explain",	"to",	"a",	      "computer.",
				 "Art",	    "is", "everything", "else", "we",	      "do" };
	int maxWidth = 20;
	Solution S;
	vector<string> res = S.fullJustify(words, maxWidth);
	vector<string> err;
	for (string s : res) {
		printf("%s\n", s.c_str());
		if (s.size() != maxWidth) {
			err.push_back(s);
		}
	}
	if (err.size() != 0) {
		printf("err line: \n");
	}
	for (string s : err) {
		printf("line size: %d line: %s\n", s.size(), s.c_str());
	}
}