68. Text Justification

题目链接

https://leetcode.com/problems/text-justification/

解题思路

模拟题

代码

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        int s = 0, e = -1, len = 0;
        for (int i = 0; i < words.size();) {
            int t = len + words[i].length() + 1;
            if (t > maxWidth + 1) {
                ans.push_back(getS(words, s, i, maxWidth));
                len = 0;
                s = i;
            } else {
                len = t;
                ++i;
            }

        }
        ans.push_back(getS(words, s, words.size(), maxWidth));
        return ans;
    }

    string getS(vector<string>& words, int s, int e, int maxWidth) {
        int space = e - s - 1;
        if (space == 0) {
            fillSpace(words[s], maxWidth - words[s].length());
            return words[s];
        }
        string ans;
        //最后一个
        if (e == words.size()) {
            for (int i = s; i < e; ++i) {
                if (i != s) {
                    ans += " ";
                }
                ans += words[i];
            }
            fillSpace(ans, maxWidth - ans.length());
        } else {
            int len = 0;
            //计算字符长度
            for (int i = s; i < e; ++i) {
                len += words[i].length();
            }
            //分配空格
            int left = maxWidth - len;
            int num = left / space, mod = left - num * space;

            for (int i = s; i < e; ++i) {
                if (i != s) {
                    fillSpace(ans, mod > 0 ? num + 1 : num);
                    mod--;
                }
                ans += words[i];
            }
        }
        return ans;
    }

    void fillSpace(string &s, int n) {
        for (int i = 0; i < n; ++i) {
            s += " ";
        }
    }
};