share my clear java solution


  • 0
    F

    The question requires us to have a clear mind.

    This solution tries to scan the words and see whether the buffer length exceeds the max width. Then add the strings and spaces into StringBuilder accordingly. And it uses slow pointer and fast pointer to indicate the positions. An invariant is kept: slow is at the start of current line while fast is at the start of next line.

    Idea similar to this.

    public class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            int slow = 0;
            int fast = slow;
            int buffer_len = 0;
            List<String> res = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            
            while (fast < words.length) {
                while (true) {
                    if (fast >= words.length) {
                        break;
                    }
                    buffer_len += words[fast].length();
                    if (buffer_len + (fast - slow) > maxWidth) {
                        buffer_len -= words[fast].length();
                        // so now fast points to the word of next line
                        break;
                    }
                    ++fast;
                }
                
                
                if (slow + 1 == fast || fast == words.length) {
                    // only one word or at the last line
                    // left-justified
                    sb.append(words[slow]);
                    ++slow;
                    while (slow < fast) {
                        sb.append(" ");
                        sb.append(words[slow]);
                        ++slow;
                    }
                    while (sb.length() < maxWidth) {
                        sb.append(" ");
                    }
                } else {
                    int spaces_available = maxWidth - buffer_len;
                    int least_spaces = spaces_available / (fast - slow - 1);
                    int extra_spaces = spaces_available % (fast - slow - 1);
                    sb.append(words[slow]);
                    ++slow;
                    while (slow < fast) {
                        for (int i = 0; i < least_spaces; ++i) {
                            sb.append(" ");
                        }
                        if (extra_spaces > 0) {
                            sb.append(" ");
                            --extra_spaces;
                        }
                        sb.append(words[slow]);
                        ++slow;
                    }
                }
                
                res.add(sb.toString());
    
                // reset, ready for next line
                sb.setLength(0);
                buffer_len = 0;
            }
            
            return res;
        }
    }
    

Log in to reply
 

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