首页 > 代码库 > 【leetcode】 Text Justification

【leetcode】 Text Justification

问题:

给定一个字符串数组words,一个整数L,将words中的字符串按行编辑,L表示每行的长度。

要求:

1)每个单词之间至少是有一个空格隔开的。
2)最后一行每个单词间只间隔一个空格, 最后一个单词后不足L长度的用空格填充。
3)除最后一行外,其他行进行填充长度的空格要均分,不能均分的,将余数代表的空格数依次填充在行左。

For example,
words["This", "is", "an", "example", "of", "text", "justification."]
L16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

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

说明:

1)边界条件要考虑,L为0,直接返回参数words。L太小一个单词都放不下也要考虑。
2)参数words为“”, L不为0, 要填充L个空格返回。(血的教训,切记)
3)这里需要弄空格填充位数的情况要再说明下,比如当前行包含的word为A、B、C、D,L = 11,则填充后的结果为:
      A$$$$B$$$$C$$$D,首先四个单词三处空格,平均后每处3个,剩余的2个要依次加在左边,向完全二叉树的定义一样,允许右子树为空,不允许左为空。

实现:

vector<string> fullJustify(vector<string> &words, int L) {

	vector<string> re;
	const int spaces = 1;
	int wordsNum = words.size();
	if(L == 0)
		return words;
	string line;
	int iword = 0;
	while (iword < wordsNum)
	{
		int i = iword;
		int cur_len = 0;
		//append word.each word divided by one space.
		while(i < wordsNum && cur_len + words[i].size() + spaces <= L + 1)
		{
			cur_len += words[i++].size() + spaces;
		}
		//L too small.
		if(cur_len == 0)
			return re;
		//last line of the text.
		if(i == wordsNum){
			line += words[iword];
			for (int k = iword + 1; k < i; ++k)
			{
				line.append(1, ' ');
				line += words[k];
			}
			line.append(L - line.size(), ' ');
		}
		else{
			int wordsLen = cur_len - (i - iword);
			int fillSpaces = L - wordsLen;
			//just one word in this line.
			if(i - iword == 1) 
			{
				line += words[iword];
				line.append(fillSpaces, ' ');
			}
			//
			else
			{
				int eqSpaces = fillSpaces / (i - iword - 1);
				int remainSpaces = fillSpaces % (i - iword - 1);
				for (int ifill = 0; ifill < i - iword - 1; ++ifill)
				{
					//eg:abcd, L = 8, eqSpaces = 8/6 = 1, remainder = 2
					// index 0  1  2  3 
					//       a  b  c  d ,  
					//a__b__c_d 
					line += words[iword + ifill];
					line.append(eqSpaces, ' ');
					if(--remainSpaces >= 0)
						line.append(1, ' ');
				}
				//last word in this line.
				line += words[i - 1];
			}
		}
		iword = i;
		re.push_back(line);
		line.clear();
	}
	return re;
}

后记:
这么个问题,用了几个小时,我cc。