C++ 0ms easy understand solution!


  • 0
    N

    num mean the size of word in current line
    sum mean the space of words use in current line
    num_extra mean the extra space in current line
    num_extra_use mean the extra space we will use right now
    num_extra_left mean the extra space we don't use
    if we can't distributed evenly, such as 8 extra space with four word ["a", "b", "c", "d"]not in the last line. We should distributed three part.
    if 8 % 3 != 0, then we will assigned one more space to the first part,
    So the first space size is 8 / 3 + 1 = 3, and
    num_extra_left = 8 - 3 = 5, num_extra = 3 - 1 = 2
    because 5 % 2 != 0
    so the next space size is 5 / 2 + 1 = 3

    class Solution {
    public:
        vector<string> fullJustify(vector<string>& words, int maxWidth) {
            vector<string> res;
            int n = words.size();
            int sum = 0;
            int num = 0;
            for (int i=0; i<n; i++) {
                sum += words[i].size();
                num++;
                if (sum + num - 1 > maxWidth || i == n - 1) {
                    if (sum + num - 1 > maxWidth) {
                        sum -= words[i].size();
                        num--;
                        i--;
                    }
                    string line = "";
                    int num_extra = maxWidth - sum;
                    int num_extra_left = num_extra;
                    for (int j=0; j<num; j++) {
                        line += words[i-num+j+1];
                        int num_extra_use = 0;
                        if (i == n - 1)
                            num_extra_use = 1;
                        if (j != num - 1 && i != n - 1)
                            num_extra_use = num_extra_left / (num - j - 1) + (num_extra_left % (num - j - 1) == 0 ? 0 : 1);
                        if (j == num - 1 && i == n - 1)
                            num_extra_use = num_extra_left;
                        line += string(num_extra_use, ' ');
                        num_extra_left -= num_extra_use;
                    }
                    line += string(num_extra_left, ' ');
                    res.push_back(line);
                    sum = 0;
                    num = 0;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.