Simple Java Solution


  • 32
    M
    public class Solution {
        public List<String> fullJustify(String[] words, int L) {
            List<String> lines = new ArrayList<String>();
            
            int index = 0;
            while (index < words.length) {
                int count = words[index].length();
                int last = index + 1;
                while (last < words.length) {
                    if (words[last].length() + count + 1 > L) break;
                    count += words[last].length() + 1;
                    last++;
                }
                
                StringBuilder builder = new StringBuilder();
                int diff = last - index - 1;
                // if last line or number of words in the line is 1, left-justified
                if (last == words.length || diff == 0) {
                    for (int i = index; i < last; i++) {
                        builder.append(words[i] + " ");
                    }
                    builder.deleteCharAt(builder.length() - 1);
                    for (int i = builder.length(); i < L; i++) {
                        builder.append(" ");
                    }
                } else {
                    // middle justified
                    int spaces = (L - count) / diff;
                    int r = (L - count) % diff;
                    for (int i = index; i < last; i++) {
                        builder.append(words[i]);
                        if (i < last - 1) {
                            for (int j = 0; j <= (spaces + ((i - index) < r ? 1 : 0)); j++) {
                                builder.append(" ");
                            }
                        }
                    }
                }
                lines.add(builder.toString());
                index = last;
            }
            
            
            return lines;
        }
    }

  • 2
    L

    How about this?

    public class Solution
    {
        public List<String> fullJustify(String[] words, int L)
        {
            final StringBuilder sb = new StringBuilder();
            for (int i = 0; i < L; ++i)
            {
                sb.append(" ");
            }
            final String pads = sb.toString();
            final List<String> strs = new ArrayList<>();
            for (int i = 0, sum = 0, j = 0; i < words.length; i = j)
            {
                for (j = i + 1, sum = words[i].length(); j < words.length && sum + j - i + words[j].length() <= L; ++j)
                {
                    sum += words[j].length();
                }
                
                final StringBuilder l = new StringBuilder();
                final int n = j - 1 - i;
                final int m = (j == words.length || 0 == n) ? 1 : ((L - sum) / n);
                final int b = (j == words.length) ? 0 : (L -sum - m * n);
                
                for (int k = i; k < j - 1; ++k)
                {
                    l.append(words[k]);
                    l.append(pads.substring(0, (k - i < b) ? (m + 1) : m));
                }
                
                l.append(words[j - 1]);
                if (j == words.length || 0 == n)
                {
                    l.append(pads.substring(0, L - sum - n));
                }
                
                strs.add(l.toString());
            }
            
            return strs;
        }
    }

  • 2
    S

    Hi would you be able to explain this logic
    spaces + ((i - index) < r ? 1 : 0 ?


  • 0
    Y
    This post is deleted!

  • 0
    Y

    we have the exact the same thought, the codes is really not nice and very likely to make mistake


  • 0
    M

    @sandeep37 when the spaces can not be divided evenly in a line between words, the empty slot on the left will be assigned more space than that on the right. For example, the extra spaces is 5, the diff = 2 (3 words), r will be 2 (5%2), spaces = 2 (5/2), then the first space slot will get 3 spaces and the second space slot will get 2 spaces. Please point out if I am wrong.


  • 12
    K

    I just cleaned up the solution. It was getting a bit tricky in the original post when it was middle justified.

    public class Solution {
        public List<String> fullJustify(String[] words, int L) {
            List<String> lines = new ArrayList<String>();
            int index = 0;
            while (index < words.length) {
                int count = words[index].length();
                int last = index + 1;
                while (last < words.length) {
                    if (words[last].length() + count + 1 > L) break;
                    //plus one for the space, if its a perfect fit it will fit
                    count += 1 + words[last].length();
                    last++;
                }
                StringBuilder builder = new StringBuilder();
                builder.append(words[index]);
                int diff = last - index - 1;
               // if last line or number of words in the line is 1, left-justified
                if (last == words.length || diff == 0) {
                    for (int i = index+1; i < last; i++) {
                        builder.append(" ");
                        builder.append(words[i]);
                    }
                    for (int i = builder.length(); i < L; i++) {
                        builder.append(" ");
                    }
                } else {
                    // middle justified
                    int spaces = (L - count) / diff;
                    int r = (L - count) % diff;
                    for (int i = index+1; i < last; i++) {
                        for(int k=spaces; k > 0; k--) {
                            builder.append(" ");
                        }
                        if(r > 0) {
                            builder.append(" ");
                            r--;
                        }
                        builder.append(" ");
                        builder.append(words[i]);
                    }
                }
                lines.add(builder.toString());
                index = last;
            }
            return lines;
        }
    }
    

  • 1
    C

    Thanks for sharing. this is my solution.

    public class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> res = new ArrayList<String>();
            char[] spaces = new char[maxWidth];
            for (int i = 0; i < maxWidth; i++){
                spaces[i] = ' ';
            }
            for (int start = 0; start < words.length;){
                int len = words[start].length();
                int end = start + 1;
                for (; end < words.length && len + 1 + words[end].length() <= maxWidth; end++){
                    len += 1 + words[end].length();
                }
                StringBuilder newStr = new StringBuilder(maxWidth);
                newStr.append(words[start]);
                int slotNum = end - start - 1;
                start++;
                if (end != words.length && slotNum != 0){
                    int evenNum = (maxWidth - (len - slotNum)) / slotNum;
                    int leftNum = (maxWidth - (len - slotNum)) % slotNum;
                    while (start < end){
                        newStr.append(spaces, 0, evenNum);
                        if (leftNum > 0){
                            newStr.append(' ');
                            leftNum--;
                        }
                        newStr.append(words[start]);
                        start++;
                    }
                } else {
                    while (start < end){
                        newStr.append(' ');
                        newStr.append(words[start]);
                        start++;
                    }
                    newStr.append(spaces, 0, maxWidth - newStr.length());
                }
                
                res.add(newStr.toString());
            }
            return res;
        }
    }
    

  • 1
    D

    @kg21mn said in Simple Java Solution:

    I just cleaned up the solution. It was getting a bit tricky in the original post when it was middle justified.

    Much easier to understand than OP's solution


  • 0
    A
    if (i < last - 1) 
    for (int j = 0; j <= (spaces + ((i - index) < r ? 1 : 0)); j++) {
                                builder.append(" ");
    }
    

    What is the logic behind the termination condition here?


  • 0
    Y

    @ayushigarg1992 According to the requirement in problem "If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.", you need to use the extra spaces r on the left side first.

    (i-index) is the number of gaps between words. when (i-index) < r, we used one extra space so j <= spaces+1. when (i-index) >= r, the extra space has been used up so j <= spaces.

    Here spaces is the total number of empty space divided by the number of gaps between words with even distribution.
    spaces = (L-count)/diff
    r is the extra space left after the even distribution.
    r = (L-count)%diff

    I hope I have made it clear.

    @ayushigarg1992 said in Simple Java Solution:

    if (i < last - 1) 
    for (int j = 0; j <= (spaces + ((i - index) < r ? 1 : 0)); j++) {
                                builder.append(" ");
    }
    

    What is the logic behind the termination condition here?


  • 0

    Can anybody tell why when there is only one word in a line, we only left-justified? I think we should put that single world in the middle.


  • 0
    E

    @kg21mn Hi, in the middle justification, what do the spaces and r variable signify? Thanks you!


  • 0
    W

    @kg21mn said in Simple Java Solution:

    builder.append(" ");

    Thanks for sharing, but why still builder.append(" "); after you add spaces and reminder spaces after the previous word?


Log in to reply
 

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