文本左右对齐

分析

这道题相对同组其他题来说比较繁琐，究其原因是因为这更像道业务逻辑题而不是算法题。我们只需要抓住三种情况：

当前行是最后一行：单词左对齐，单词间有且仅有一个空格。其余空格在末尾补充从而对齐。
当前行不是最后一行，但只有一个单词：该单词左对齐，在末尾填充空格从而对齐。
当前行不是最后一行且不止一个单词：设当前单词数为 num_words，单词间空格数为 num_spaces 。因为我们要在单词周围均匀分配空格，所以单词之间至少有空格 $\mathrm{avg\_spaces} = \frac{\mathrm{num\_spaces}}{\mathrm{num\_words - 1}}$ 对于多出来的空格 $\mathrm{extra\_spaces} = \mathrm{num\_spaces}\bmod{(\mathrm{num\_words} - 1)}$ ，应该填充在前 extra_spaces 个单词的之间。也就是说，前 extra_spaces 个单词应该填充 avg_spaces + 1 个空格，其余的单词应该填充 avg_spaces 个空格。

解答

1
class Solution {
2
private:
3
  auto blank(int n) { return string(n, ' '); }
4
  auto join(const vector<string> &words, int left, int right,
5
            const string &sep) {
6
    auto s = words[left];
7
    for (auto i = left + 1; i < right; ++i)
8
      s += sep + words[i];
9

10
    return s;
11
  }
12

13
public:
14
  vector<string> fullJustify(vector<string> &words, int maxWidth) {
15
    vector<string> ans;
16
    auto right = 0;
17
    int n = words.size();
18
    while (true) {
19
      auto left = right;
20
      auto sum_len = 0;
21

22
      while (right < n &&
23
             sum_len + words[right].length() + right - left <= maxWidth)
24
        sum_len += words[right++].length();
25

26
      if (right == n) {
27
        auto s = join(words, left, n, " ");
28
        ans.emplace_back(s + blank(maxWidth - s.length()));
29
        return ans;
30
      }
31

32
      auto num_words = right - left;
33
      auto num_spaces = maxWidth - sum_len;
34

35
      if (num_words == 1) {
36
        ans.emplace_back(words[left] + blank(num_spaces));
37
        continue;
38
      }
39

40
      auto avg_spaces = num_spaces / (num_words - 1);
41
      auto extra_spaces = num_spaces % (num_words - 1);
42
      auto s1 =
43
          join(words, left, left + extra_spaces + 1, blank(avg_spaces + 1));
44
      auto s2 = join(words, left + extra_spaces + 1, right, blank(avg_spaces));
45
      ans.emplace_back(s1 + blank(avg_spaces) + s2);
46
    }
47
  }
48
};