Easy and Concise Java AC Solution


  • 0
    H
    public class Solution {
        private List<String> res;
        public List<String> fullJustify(String[] words, int maxWidth) {
            res = new ArrayList<>();
            // Start index for current line
            int start = 0;
            // number of word for current line
            int count = 0;
            // required width current line need, include one space between two words
            int required = 0;
            for (int i = 0; i < words.length; i++) {             
                required += words[i].length() + ((i != start) ? 1 : 0);            
                if (required > maxWidth) {
                    // from words[start] tp words[i - 1] is a valid line, add to res
                    addToRes(words, start, i - 1, count, required - words[i].length() - 1, maxWidth);
                    // clear
                    start = i;
                    count = 0;
                    required = 0;
                    // stay still, words[i] has not been used yet.
                    i--;
                } else {
                    count++;
                }
            }
            // handle last line
            addToRes(words, start, words.length - 1, count, required, maxWidth);
            return res;
        }
    
        private void addToRes(String[] words, int start, int end, int count, int required, int maxWidth) {
            StringBuilder candidate = new StringBuilder("");
            // one word case and last line case need left-justified.
            if (count == 1 || end == words.length - 1) {
                for (int i = start; i <= end; i++) {
                    candidate.append(words[i]);
                    if (i != end) {
                        candidate.append(" ");
                    }
                }
                for (int j = 0; j < maxWidth - required; j++) {
                  candidate.append(" ");
                }
                res.add(candidate.toString());
                return;
            }
            // every partition amortise the space, if there are extra, give them to left guys.
            int spacePerPartition = (maxWidth - required) / (count - 1);
            int spaceExtra = maxWidth - required - (count - 1) * spacePerPartition;
            for (int i = start; i <= end; i++) {
                candidate.append(words[i]);
                if (i != end) {
                    candidate.append(" ");
                    for (int j = 0; j < spacePerPartition; j++) {
                        candidate.append(" ");
                    }
                    if (i - start < spaceExtra) {
                        candidate.append(" ");
                    }
                }
            }
            res.add(candidate.toString());
        }
    }
    

Log in to reply
 

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