Easy to understand JAVA solution


  • 0
    Z

    To solve the problem, first to think about how to solve the problem without extra padding spaces.

    e.g. ["This", "is", "an", "example", "of", "text", "justification."]

    "This" -> 4 characters, len(" ") + len("This") - 1
    "This is" -> 7 characters, len(" ") + len("is")
    "This is an" -> 10 characters, len(" ") + len("an")

    Therefore, we can make a virtual space at the beginning when count the number of characters. That is, count = -1 at beginning, each time count += len(word) + 1. If previous count plus current words exceed the maxWidth, we know that it cannot add new word now. We should try to start a new line.

    But before starting a new line, let us think about adding the extra padding spaces. It should be evenly distributed between the words. Therefore, it should have the following three conditions:

    1. Only one word in current line. We just need to add all spaces at the end. e.g. maxWidht = 6, current line: "This "
    2. There are n words in current line. n - 1 spaces between them already in the above example.
      Such as "This is an", 2 spaces added already, and we should try to insert padding spaces in that
      2 hole position. First we see there are how many spaces left,
      1. less than n-1 spaces left. That means we should satisfy the left holes first, we can do it by just adding one space hole by hole until we used up all the spaces.
      2. more than n - 1 spaces left. That means each hole, we can add at least k / (n-1) spaces. After adding it to each hole. We now left k % (n - 1) spaces. We back to the condition 1)
    3. current line is the last line. We simply just add the string, and then padding all the spaces to the end.

    The code looks like this, I think it is quite easy to understand:

    public class Solution {
        
        private String construct(String[] words, int start, int end, int count, int maxWidth) {
            StringBuilder sb = new StringBuilder();
            if(start == end) {
                sb.append(words[start]);
                int size = sb.length();
                for(int i = 0; i < maxWidth - size; i++)
                    sb.append(" ");
            } else {
                int evenSpace = (maxWidth - count) / (end - start);
                int nonEvenSpace = (maxWidth - count) % (end - start);
                for(int i = start; i <= end; i++) {
                    if(i != start) {
                        sb.append(" ");
                        for(int j = 0; j < evenSpace; j++) sb.append(" ");
                        if(nonEvenSpace > 0) { sb.append(" "); nonEvenSpace--; }
                    }
                    sb.append(words[i]);
                }
            }
    
            return sb.toString();
        }
        
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> result = new ArrayList<>();
            if(words == null || words.length == 0 || maxWidth == 0) {
                result.add("");
                return result;
            }
                
            int lastSeen = -1;
            int count = -1;
    
            int j = 0;
            while(j < words.length) {
                int len = 1 + words[j].length();
                if(count + len > maxWidth) {
                    result.add(construct(words, lastSeen+1, j-1, count, maxWidth));
                    count = -1;
                    lastSeen = j - 1;
                }
                count += len;
                j++;
            }
            
            StringBuilder sb = new StringBuilder();
            for(int i = lastSeen + 1; i < j; i++) {
                if(i != lastSeen + 1) {
                    sb.append(" ");
                }
                sb.append(words[i]);
            }
            for(int i = 0; i < maxWidth - count; i++)   sb.append(" ");
            result.add(sb.toString());
            return result;
        }
    }
    

Log in to reply
 

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