Java Solution with Comment


  • 0
    R
    public class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            // 1. Each line should has exactly maxWidth characters
            // 2. Put as many words as you can in each line, between two words there must be at least one space
            // 3. Spaces between words should be distributed as evenly as possible
            // 4. If spaces cannot be distributed evenly, place more spaces on the left-most slot
            // 5. If a line other than the last line has onlt one word, it should be left-justified
            // 6. The last line should be left justified and no extra spaces should be inserted between the words
            // (but still needs a space to seperate two words)
    
            int idx = 0;
            int curLen = 0;
            List<String> cur = new ArrayList<>();
            List<String> ans = new ArrayList<>();
            while (idx != words.length) {
                // if the current word is not the last word and adding the current word into the list would not exceed the max width,
                // then we add the current word into the current list
                while (idx != words.length && curLen + words[idx].length() <= maxWidth) {
                    cur.add(words[idx]);
                    curLen += words[idx].length() + 1; // +1 means we should add a space behind each space
                    idx++;
                }
                curLen--; // current length minus 1, the last word shouldn't come with a space behind it
                // the last line, left justification
                if (idx == words.length) {
                    StringBuilder sb = new StringBuilder();
                    // process words except the last one, because the last one should not be followed by a space
                    for (int i = 0; i < cur.size() - 1; i++) {
                        sb.append(cur.get(i) + " ");
                    }
                    // process the last word
                    sb.append(cur.get(cur.size() - 1));
                    // after processing the words, add extra spaces to the end to make it fullt justified
                    for (int i = maxWidth - curLen; i > 0; i--) {
                        sb.append(" ");
                    }
                    ans.add(sb.toString());
                }
                else {
                    // if a line just contains one word -> left justification
                    if (cur.size() == 1) {
                        StringBuilder sb = new StringBuilder();
                        sb.append(cur.get(0));
                        for (int i = maxWidth - cur.get(0).length(); i > 0; i--) {
                            sb.append(" ");
                        }
                        ans.add(sb.toString());
                    }
                    else {
                        int numOfSlots = cur.size() - 1;
                        StringBuilder sb = new StringBuilder();
    
                        int index = 0;
                        // if the spaces cannot distributed evenly, we place more spaces on the leftmost slot.
                        // keep doing this until the rest can be distributed evenly
                        while (index != cur.size() - 1 && (maxWidth - curLen) % numOfSlots != 0) {
                            int k = (int)(Math.ceil((double)(maxWidth - curLen) / (double)numOfSlots));
                            sb.append(cur.get(index) + " ");
                            curLen += k;
                            while (k > 0) {
                                sb.append(" ");
                                k--;
                            }
                            numOfSlots--;
                            index++;
                        }
                        // the extra spaces can be distributed evenly
                        int k = (maxWidth - curLen) / numOfSlots;
                        for (; index < cur.size() - 1; index++) {
                            sb.append(cur.get(index) + " ");
                            for (int j = k; j > 0; j--) {
                                sb.append(" ");
                            }
                        }
                        sb.append(cur.get(cur.size()-1));
                        ans.add(sb.toString());
                    }
                }
                // reset the current list and current length
                cur.clear();
                curLen = 0;
            }
            return ans;
        }
    }
    

Log in to reply
 

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