首页 > 代码库 > 【LeetCode】Text Justification
【LeetCode】Text Justification
Text Justification
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 exactlyL 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.
click to show corner cases.
- A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.
贪心算法，不难，繁琐，主要这几步骤：
使用字符串cur记录当前行
1、计算能否加入下一个单词word
2、若长度L能容纳，则加入cur，并更新cur长度
3、若长度L不能容纳，则cur即为符合条件的一行，并重新调整单词间隔
(1)cur不止一个单词，则让最后一个单词靠右对齐。由于左间隔不小于右间隔，因此左间隔取均分空格数的上界。
(2)cur只有一个单词，在尾部加入空格。
4、单词全部添加完毕，在cur尾部加入空格。
class Solution {public: vector<string> fullJustify(vector<string> &words, int L) { vector<string> result; if(words.empty()) return result; else if(words.size() == 1) { string str = words[0]; int space = L-str.size(); string spaceStr(space, ‘ ‘); result.push_back(str+spaceStr); return result; } else { int ind = 0; //index of word to be added to result int num = 0; //number of words gathered into cur line int count = 0; //number of chars in cur line string cur; while(ind < words.size()) { while(ind < words.size()) {//add words[ind] int tempCount; if(num != 0) { tempCount = count+1+words[ind].size(); if(tempCount > L) break; else { count = tempCount; cur += " "; cur += words[ind]; } } else { count = words[ind].size(); cur += words[ind]; } ind ++; num ++; } if(ind == words.size()) {//case1: ind == words.size(), deal with the last word break; } else {//case2: count+1+words[ind].size() > L //justify the last line, rebuild cur cur = ""; int totalSpace = L-count+(num-1); while(num) { cur += words[ind-num]; int space; if(num != 1) { space = totalSpace/(num-1); //left space is no less than evenly divided if(space*(num-1) < totalSpace) space += 1; } else space = totalSpace; string spaceStr = string(space, ‘ ‘); cur += spaceStr; num --; totalSpace -= space; } result.push_back(cur); //begin next line cur = ""; num = 0; cur += words[ind]; count = words[ind].size(); ind ++; num ++; } } //deal with the last word int space = L-count; string spaceStr(space, ‘ ‘); result.push_back(cur+spaceStr); return result; } }};
【LeetCode】Text Justification