题目描述

题目链接：68. Text Justification

Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth 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 maxWidth 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.

例子

例子 1

Input: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 Output: [ "This is an", "example of text", "justification. " ]

例子 2

Input: words = ["What","must","be","acknowledgment","shall","be"] maxWidth = 16 Output: [ "What must be", "acknowledgment ", "shall be " ] Explanation: Note that the last line is “shall be " instead of “shall be”, >because the last line must be left-justified instead of fully-justified. >Note that the second line is also left-justified becase it contains only one word.

例子 3

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

Note

• A word is defined as a character sequence consisting of non-space characters only.
• Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
• The input array words contains at least one word.

解题思路

这道题虽然标注的难度是 hard，但是实际上思路还是比较清晰的，主要解决三个问题：

• 根据规则确定当前行 line 要用的单词 -> 这里可以用双指针的思路，slow 指向当前行第一个单词，fast 从 slow 开始往后遍历并依次将当前单词长度加至字符串长度 len，直到 len + words[fast] + num_of_spaces > maxWidth，这里所需要最小的空格个数是 fast - slow - 1
• 有了当前行的单词之后，只需要根据规则将其分布即可：有以下几种情况：
  • fast == words.end()：意味着到了最后一行，那么 line 为一个单词接一个空格接下一个单词，剩余空格放最后即可
  • fast == slow + 1：即只有一个单词，那么 line = words[slow] + ' ' * maxWidth - len(words[slow])
  • 通常情况下，首先计算出每个 gap （gap 总共有 (fast - slow - 1) 个）至少分配的空格数 base_spaces = (maxWidth - len) / n(gap)，再将剩余的空格数 base_spaces = (maxWidth - len) % n(gap) 从前后往后在每个 gap 加进去直到加完为止即可。

代码如下：

#include <string>
#include <vector>

class Solution {
public:
    std::vector<std::string> fullJustify(std::vector<std::string>& words, int maxWidth) {
        int slow = 0, fast = 0;
        int curLen = 0;
        int count = 0;
        std::string line;
        std::vector<std::string> text;
        while (fast < words.size()) {
            curLen = 0;             // current length for all chosen words
            int min_spaces = 0;    // min number of spaces we need for current line

            // keep adding next word to current line until it reach maxWidth
            while (fast < words.size() && curLen + words[fast].length() + min_spaces <= maxWidth) {
                min_spaces++;
                curLen += words[fast].length();
                fast++;
            }

            // we reach the last line
            if (fast == words.size()) break;

            // only 1 word in line
            if (fast == slow + 1) {
                line = words[slow];
                line += std::string(maxWidth - words[slow].length(), ' ');
            } else { // more than 1 word in line
                int count_gap = fast - slow - 1;
                int base_spaces = (maxWidth - curLen) / count_gap;  // should be at least 1
                int res_spaces = (maxWidth - curLen) % count_gap;
                for (int i = slow; i < fast - 1; i++) {
                    line += words[i];
                    line += std::string(base_spaces, ' ');
                    if (res_spaces) {
                        line += ' ';
                        res_spaces--;
                    }
                }
                line += words[fast - 1];
            }
            text.push_back(line);
            line = "";
            slow = fast;
        }

        // add last line
        for (int i = slow; i < fast - 1; i++) {
            line += words[i];
            line += ' ';
        }
        line += words[fast - 1];
        line += std::string(maxWidth - line.length(), ' ');
        text.push_back(line);

        return text;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

GitHub 代码同步地址： 68.TextJustification.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions