LeetCode_068: Text Justification

又是一道通过率不过20%的题,总结这种通过率比较多的题目,发现其中很多原理并不难,导致通过率比较低的原因是各种极端情况,还有就是题目理解和表述不够清晰。比如自己实现Atoi,如果列出要处理的各种情况,写出来并不难。这道题也是一样,其实没什么难度,只是有些情况下,具体说来就是最后一行或者一行的最后一个单词,需要特殊处理。

题目

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[ “This is an”, “example of text”, “justification. ” ]

Note: Each word is guaranteed not to exceed L in length.

分析

本来第一个版本写了50line,发现text case 中要最后一行紧贴着输出,然后为了处理最后一行相当于把前面的代码都复制了一遍。

下面的代码主要分为两部分,第一部分是把单词划分到每一行,第二部分是加空格,形成最后的显示输出。因为两部分分开了,所以是一个离线算法,这样看的清楚一些。在实际应用中会把两部分柔和起来,一方面成为在线算法,实时处理,另一方面,可以减少占用的空间资源。

代码

class Solution {
public:
	vector<string> fullJustify(vector<string>& words, int maxWidth){
		if (words.empty() || maxWidth == 0){
			return words;
		}

		vector<string> text, line;
		vector<pair<vector<string>, int>> lines;

		const int n = words.size();
		int curWidth = 0, spaceWidth = maxWidth;
		int lnum = 0;
		for (int i = 0; i < n; ++i){
			int wlen = words[i].size();
			if (curWidth + wlen == maxWidth){
				line.push_back(words[i]);
				lines.push_back({ line, spaceWidth - wlen });
				line.clear();
				curWidth = 0;
				spaceWidth = maxWidth;
			}
			else if (curWidth + wlen > maxWidth){
				lines.push_back({ line, spaceWidth });
				line.clear();
				curWidth = 0;
				spaceWidth = maxWidth;
				--i;
			}
			else if (curWidth + wlen < maxWidth){
				line.push_back(words[i]);
				spaceWidth -= wlen;
				curWidth += (wlen + 1);
			}
		}

		if (!line.empty()){
			lines.push_back({ line, spaceWidth });
		}

		for (int i = 0; i < lines.size() - 1; ++i){
			string textline;
			line = lines[i].first;
			spaceWidth = lines[i].second;
			if (line.size() == 1){
				textline += line[0];
				while (spaceWidth){
					spaceWidth--;
					textline += " ";
				}
				text.push_back(textline);
			}
			else{
				int spaceL = spaceWidth / (line.size() - 1);
				int spaceR = spaceWidth % (line.size() - 1);
				for (int j = 0; j < line.size(); ++j){
					int space = spaceL;
					if (spaceR){
						spaceR--;
						space++;
					}
					textline += line[j];
					
					while (space && j != line.size() - 1){
						space--;
						textline += " ";
					}
					
				}
				text.push_back(textline);
			}
		}

		if (!lines.empty()){
			string textline;
			line = lines[lines.size() - 1].first;
			spaceWidth = lines[lines.size() - 1].second;
			if (line.size() == 1){
				textline += line[0];
				while (spaceWidth){
					spaceWidth--;
					textline += " ";
				}
				text.push_back(textline);
			}
			else{
				for (int i = 0; i < line.size(); ++i){
					spaceWidth--;
					textline += line[i];
					textline += " ";
					while (spaceWidth && i == line.size() - 1){
						spaceWidth--;
						textline += " ";
					}
				}
				text.push_back(textline);
			}
		}

		return text;
	}
};

 

发表评论