Classic Interview 150 Questions P68 Text Justification

---

Timeline

Timeline

2025-11-10

init

Array, String

---

Problem:

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 follow each word.

#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 fit in the current line, 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, a total of 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 the space after the last word
					curr.pop_back();
				}
				// Add the remaining spaces 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());
	}
}