# 凌云的博客

## LeetCode 算法题 68. 文本左右对齐

### 题目

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

``````输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16

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

``````输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16

[
"What   must   be",
"acknowledgment  ",
"shall be        "
]

因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
``````

``````输入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20

[
"Science  is  what we",
"understand      well",
"enough to explain to",
"a  computer.  Art is",
"everything  else  we",
"do                  "
]
``````

### 解法

``````class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> ret;
int currentLen = 0, begin = 0, i = 0;
for (; i < words.size(); ++i) {
if (currentLen + words[i].size() + (i - begin) > maxWidth) {
packToLine(words, begin, i, currentLen, maxWidth, ret);
begin = i;
currentLen = words[i].size();
} else {
currentLen += words[i].size();
}
}

lastPack(words, begin, words.size(), currentLen, maxWidth, ret);
return ret;
}

void packToLine(vector<string> &words, int begin, int end, int currentLen, int maxWidth, vector<string> &ret) {
const int space = maxWidth - currentLen;
if (end == begin + 1) {
string s = words[begin];
s.append(space, ' ');
ret.push_back(s);
return;
}

int pad = space / (end - begin - 1);
int extra = space % (end - begin - 1);
string s;
for (int i = begin; i < end - 1; ++i) {
s += words[i];
if (extra) {
s.push_back(' ');
--extra;
}
}

s += words[end - 1];
ret.push_back(s);
}

void lastPack(vector<string> &words, int begin, int end, int currentLen, int maxWidth, vector<string> &ret) {
int space = maxWidth - currentLen;
string s;
for (int i = begin; i < end; ++i) {
s += words[i];
if (space) {
s.push_back(' ');
--space;
}
}

if (space)
s.append(space, ' ');

ret.push_back(s);
}
};
``````