Share my concise c++ solution - less than 20 lines


  • 106
    Q
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> res;
        for(int i = 0, k, l; i < words.size(); i += k) {
            for(k = l = 0; i + k < words.size() and l + words[i+k].size() <= L - k; k++) {
                l += words[i+k].size();
            }
            string tmp = words[i];
            for(int j = 0; j < k - 1; j++) {
                if(i + k >= words.size()) tmp += " ";
                else tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' ');
                tmp += words[i+j+1];
            }
            tmp += string(L - tmp.size(), ' ');
            res.push_back(tmp);
        }
        return res;
    }
    

    For each line, I first figure out which words can fit in. According to the code, these words are words[i] through words[i+k-1]. Then spaces are added between the words. The trick here is to use mod operation to manage the spaces that can't be evenly distrubuted: the first (L-l) % (k-1) gaps acquire an additional space.


  • 75
    M

    Great solution. Thanks for sharing.

    Here's a Java version:

    public class Solution {
        public List<String> fullJustify(String[] words, int L) {
            List<String> list = new LinkedList<String>();
            
            for (int i = 0, w; i < words.length; i = w) {
                int len = -1;
                for (w = i; w < words.length && len + words[w].length() + 1 <= L; w++) {
                    len += words[w].length() + 1;
                }
                
                StringBuilder strBuilder = new StringBuilder(words[i]);
                int space = 1, extra = 0;
                if (w != i + 1 && w != words.length) { // not 1 char, not last line
                    space = (L - len) / (w - i - 1) + 1;
                    extra = (L - len) % (w - i - 1);
                }
                for (int j = i + 1; j < w; j++) {
                    for (int s = space; s > 0; s--) strBuilder.append(' ');
                    if (extra-- > 0) strBuilder.append(' ');
                    strBuilder.append(words[j]);
                }
                int strLen = L - strBuilder.length();
                while (strLen-- > 0) strBuilder.append(' ');
                list.add(strBuilder.toString());
            }
            
            return list;
        }
    }

  • 6
    M

    Thanks. (L-l) % (k-1) to add extra space is very brilliant.


  • 1

    Hi, qddpx. Thanks for your sharing! Really brilliant codes! I think besides (L - l) % (k - 1) mentioned by mcrystal, l + words[i+k].size() <= L - k is also very clever since it unifies both cases of a single word multiple words (and thus spaces are required)


  • 0

    The nice structure and variable names make the code easy to understand. BTW, int len = -1; is so clerver :-)


  • 2
    M
    len = -1 
    

    is really brilliant


  • 0
    P

    what are i,j,l,k meaning ? it's better make some comments.


  • 32
    J

    Added some explanation in comments for ease of understanding

    public class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> ret = new ArrayList<>();
            if(words.length == 0 || maxWidth == 0) {
                ret.add(""); //for some reason OJ expects list with empty string for empty array input
                return ret;
            }
    
            for(int i = 0, w; i < words.length; i = w) {
                int len = -1; //We need to skip the space for last word hence start len = -1
                //check how many words fit into the line
                for(w = i; w < words.length && len + words[w].length() + 1 <= maxWidth; w++) {
                    len += words[w].length() + 1; // 1 extra for the space
                }
            
                //calculate the number of extra spaces that can be equally distributed
                //also calculate number of extra spaces that need to be added to first few
                //words till we fill the line width
                //For example line width is 20 we have three words of 3 4 2 4 length
                //[our_,life_,is_,good_,_,_,_,_,] ==> [our_,_,_,life_,_,_is_,_,good] 
                //   Note _, indicates space
                //Count number of empty spaces at end of line:= width-len = 20-(15) = 5 
                //These five spaces need to be equally distributed between 4-1 = 3 gaps
                //n words will have n-1 gaps between them
                // 5 / 3 = 1 extra space between each word (in addition to default 1 space, 
                //                                          total space count = 2)
                // 5 % 3 = 2 extra spaces between first three words as shown above
    
                int evenlyDistributedSpaces = 1; //If we don't enter loop at line # 37 then we need to have default value
                int extraSpaces = 0;
                int numOfGapsBwWords = w-i-1; //w is already ponting to next index and -1 since
                                              //n words have n-1 gaps between them
                                              
                //Moreover we don't need to do this computation if we reached the last word
                //of array or there is only one word that can be accommodate on the line
                //then we don't need to do any justify text. In both cases text can be left,
                //left-aligned 
                                            
                if(w != i+1 && w != words.length) {
                    //additional 1 for the default one space between words
                    evenlyDistributedSpaces = ((maxWidth-len) / numOfGapsBwWords) + 1;
                    extraSpaces = (maxWidth-len)%numOfGapsBwWords;
                }
        
                StringBuilder sb = new StringBuilder(words[i]);
                for(int j = i+1; j < w; j++) {
                    for(int s = 0; s < evenlyDistributedSpaces; s++) {
                        sb.append(' ');
                    }
                    if(extraSpaces > 0) {
                        sb.append(' ');
                        extraSpaces--;
                    }
                    sb.append(words[j]);
                }
                
                //Handle the above two cases we skipped, where there is only one word on line
                //or we reached end of word array. Last line should remain left aligned.
                int remaining = maxWidth-sb.length();
                while(remaining > 0) {
                    sb.append(' ');
                    remaining--;
                }
                ret.add(sb.toString());
            }
            return ret;
        }
    }
    

  • 9

    @melvin.ming.gong The calculation of space and extra is a little confusing to me, so I made a slight change. Here is the variation with comments for your reference. Thanks for your sharing!

        //   0   1  2    3
        // "This is an example..."
        //  i=0, j=3, width=8, space=(16-8)/(3-0-1)=4, extra=0
        // ------------------------------------------------------
        //   3      4   5        6
        // "example of text justification."
        //  i=3, j=6, width=13, space=(16-13)/(3-0-1)=1, extra=1
        // ------------------------------------------------------
        // "justification."
        //  i=6, j=7, space=1, extra=0
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> result = new ArrayList<>();
            for (int i = 0, j; i < words.length; ) {
                int width = 0;                                  // width of words without space
                for (j = i; j < words.length && width + words[j].length() + (j - i) <= maxWidth; j++)
                    width += words[j].length();                 /* j is the next word */
                
                int space = 1, extra = 0;                       // for last line, space=1
                if (j - i != 1 && j != words.length) {          // not 1 word (div-by-zero) and not last line
                    space = (maxWidth - width) / (j - i - 1);   // minus 1 to exclude skip last word
                    extra = (maxWidth - width) % (j - i - 1);
                }
                
                StringBuilder line = new StringBuilder(words[i]);
                for (i = i + 1; i < j; i++) {                   // move i to j finally
                    for (int s = space; s > 0; s--) line.append(" ");
                    if (extra-- > 0) line.append(" ");
                    line.append(words[i]);
                }
                for (int s = maxWidth - line.length(); s > 0; s--) line.append(" ");
                result.add(line.toString());
            }
            return result;
        }
    

  • 7
    R

    A readable C++ version:

    class Solution {
    public:
        vector<string> fullJustify(vector<string>& words, int maxWidth) {
            vector<string> result;
            for(int i = 0, j; i < words.size(); i = j) {
                int width = 0;
                for(j = i; j < words.size() && width + words[j].size() + j - i <= maxWidth; j++) {
                    width += words[j].size();
                }
                int space = 1, extra = 0;
                if(j - i != 1 && j != words.size()) {
                    space = (maxWidth - width) / (j - i - 1);
                    extra = (maxWidth - width) % (j - i - 1);
                }
                string line(words[i]);
                for(int k = i + 1; k < j; k++) {
                    line += string(space, ' ');
                    if(extra-- > 0) {
                        line += " ";
                    }
                    line += words[k];
                }
                
                line += string(maxWidth - line.size(), ' ');
                result.push_back(line);
            }
            return result;
        }
    };
    

  • 0
    G

    As others have already applauded solution is very neat. Apart from that I have newly learnt that the operators && and || can be substituted now with "and" and "or" respectively. Wow!


  • 0
    D

    @G513 Do you know why it can be replaced using "and"? Is this a C++ thing?


  • 3

    This question is actually not hard... But I didn't figure it out in a period of acceptable time.

    Your solution is exactly the same as mine, but much more elegant, thanks for your sharing.

    Below is the Java version with comment:

    public List<String> fullJustify(String[] words, int L) {
            List<String> res = new ArrayList();
            for (int i = 0, k; i < words.length; i = k) {
                // i: the index of word 
                // k: the current index of words in the line
                // len: current total len of words in the line
                int len = -1;
                for (k = i; k < words.length && len + words[k].length() + 1 <= L; k++) {
                    len += words[k].length() + 1;
                }
                StringBuilder curStr = new StringBuilder(words[i]);
                int space = 1, extra = 0;
                // not 1 char, not last line
                if (k != i + 1 && k != words.length) {
                    space = (L - len) / (k - i - 1) + 1; // 1 is for another space
                    extra = (L - len) % (k - i - 1);
                }
                // not 1 char, including last line, initialize space == 1 is to deal with last line case.
                for (int j = i + 1; j < k; j++) { // j: index of word in the current line
                    for (int s = space; s > 0; s--) curStr.append(" "); // add the "even" space
                    if (extra-- > 0) curStr.append(" ");
                    curStr.append(words[j]);
                }
                // if it's the last line
                int strLen = L - curStr.length();
                while (strLen-- > 0) curStr.append(" ");
                res.add(curStr.toString());
            }
            return res;
        }
    

  • 0

    What an elegant solution!!! Good job!


  • 0
    J

    This line is wonderful
    tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' ');


  • 0
    Q

    One more solution that is concise and straightforward.
    pre-allocate string with all space.

    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        for (int i = 0, sz = words.size(); i < sz;) {
            int cnt = words[i].size();
            int j = i;
            for (++i; i < sz && cnt + words[i].size() + 1 <= maxWidth; ++i) { cnt += words[i].size() + 1; }
            string s (maxWidth, ' ');
            int n_space = 1, one_more = 0;
            if (i != sz && i - j > 1) n_space = 1 + (maxWidth - cnt) / (i - j - 1), one_more = (maxWidth - cnt) % (i - j - 1);
            auto p = s.begin();
            for (; j < i; ++j) {
                for (auto ch: words[j]) { *p++ = ch; }
                p += n_space + (one_more-- > 0);
            }
            res.push_back(std::move(s));
        }
        return res;
    }

  • 1
    T

    @JadenPan can you tell me tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' '); that (j < (L - l) % (k - 1) is what meaning? Thank you.


  • 0
    K

    @Tomecs since there are k words,that means there are k-1 slots and the extra characters are (total length of line)-total no of characters in all the words in that line) which is nothing but L-l and k-1 here refers to total slots as there are k words,
    for example,consider the below case,
    <word>....<word>.....<word>....<word> and there are 8 extra characters,how would you distribute them...?
    <word> 1st extra char <word> 2nd extra char <word> 3rd..<word>
    <word> 4th..<word> 5th..<word> 6th <word>
    <word> 7th <word> 8th......right..?
    which is nothing but l-l/k-1 for words greater than 8%3=2;


  • 0

    https://discuss.leetcode.com/topic/110789/missing-test-case
    All the solutions in the most upvoted post can't pass this missing test case

    Input:
    ["a","b","c","d"]
    3
    Output:
    ["a b","c d"]

    This output violates the following description:

    For the last line of text, it should be left justified and no extra space is inserted between words.

    What's the right answer for this test case?


  • 0
    M

    Similarly, here's my Java Code

            public List<String> fullJustify(String[] words, int maxWidth) {
    		List<String> res = new ArrayList<>();
    		if (words == null || words.length == 0 || maxWidth < 0) return res;
    		int n = words.length;
    		int s = 0, e = 0;
    		for (s = 0; s < n; s = e) {
    			int len = -1;
    			for (e = s; e < n && len + words[e].length() + 1 <= maxWidth; ++e) {
    				len += words[e].length() + 1;
    			}
    			int space = 1;
    			int extra = 0;
    			if (e != s + 1 && e != n) {
    				space = (maxWidth - len) / (e - s - 1) + 1;
    				extra = (maxWidth - len) % (e - s - 1);
    			}
    			StringBuilder row = new StringBuilder(words[s]);
    			for (int i = s + 1; i < e; ++i) {
    				addSpaces(row, space);
    				if (--extra >= 0) row.append(' ');
    				row.append(words[i]);
    			}
    			addSpaces(row, maxWidth - row.length());
    			res.add(row.toString());
    		}
    		return res;
    	}
    	private void addSpaces(StringBuilder row, int cnt) {
    		while (cnt-- > 0) {
    			row.append(' ');
    		}
    	}
    

Log in to reply
 

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