Share my concise solution, this is easy, should it classify to be hard ?


  • 0
    S
    vector<string> fullJustify(vector<string> &words, int L) {
            vector<string> ans, vs;
            string str;
            int len = 0, div = 0, mod = 0;
            
            for (int i = 0; i < words.size(); ++i) {
                if (len + vs.size() + words[i].size() <= L) {
                    vs.push_back(words[i]);
                    len += words[i].size();
                }
                else {
                    if (vs.size() == 1) {
                        str = vs[0];
                        str.append(L - str.size(), ' ');
                        ans.push_back(str);
                    }
                    else if (vs.size() > 1) {
                        div = (L - len) / (vs.size() - 1);
                        mod = (L - len) % (vs.size() - 1);
                        str = vs[0];
                        for (int j = 1; j < vs.size(); ++j) {
                            if (j <= mod) str.append(div+1, ' '); // one more space
                            else str.append(div, ' ');
                            str += vs[j];
                        }
                        ans.push_back(str);
                    }
                    
                    vs.clear();
                    vs.push_back(words[i]);
                    len = words[i].size();
                }
            }
            
            // add the last line
            // left justified and no extra space is inserted between words
            str = vs[0];
            for (int i = 1; i < vs.size(); ++i) {
                str += ' ' + vs[i];
            }
            str.append(L-str.size(), ' ');
            ans.push_back(str);
            return ans;
        }

  • 2
    F

    Basically we go through the String array of words and check whether the length of this line + # of spaces + length of next word is bigger than L. If not, just add the word and update length. Otherwise, we build this line and append the word to next line.

    Note the calculation of spaces between words. We divide the rest length of current line with the # of interval between words, which is line.size() - 1. # of spaces between words can be just quotient, or quotient + 1 if we still have remainder.

    Here is my Java implementation of your idea.

    public static List<String> fullJustify(String[] words, int L) {
        List<String> res = new ArrayList<String>();
        if (words == null || words.length == 0 || L < 0) return res;
        List<String> line = new ArrayList<String>();
        String str = "";
        int len = 0, div, mod;
        for (int i = 0; i < words.length; i++) {
            if (len + line.size() + words[i].length() <= L) {
                line.add(words[i]);
                len += words[i].length();
            } else {
                if (line.size() == 1) { // only 1 word in this line
                    str = line.get(0);
                    for (int j = L - str.length(); j > 0; j--) str += " ";
                } else if (line.size() > 1) {
                    div = (L - len) / (line.size() - 1);
                    mod = (L - len) % (line.size() - 1);
                    str = line.get(0); // append first word
                    for (int j = 1; j < line.size(); j++) { // append remaining words
                        for (int k = 0; k < div; k++) str += " ";
                        if (j <= mod) str += " "; // append 1 more space
                        str += line.get(j);
                    }
                }
                res.add(str);
                line.clear();
                line.add(words[i]); // next line
                len = words[i].length();
            }
        }
        // last line
        str = line.get(0);
        for (int i = 1; i < line.size(); i++) str += " " + line.get(i);
        for (int i = L - str.length(); i > 0; i--) str += " ";
        res.add(str);
        return res;
    }

Log in to reply
 

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