My Accepted Java solution


  • 0
    Y

    Algorithm: sweep the words array, pointer j for the first word of each line, pointer i is the current word going forward...time complexity is O(n), space complexity is O(1).

    public class Solution {
    public List<String> fullJustify(String[] words, int L) {
        
        List<String> list = new ArrayList<String>();
        
        int i=0;
        int j=0;
        int total = 0;
        while(i<words.length)
        {
            int len = words[i].length();
            
            if(total + len + i - j >= L)
            {
                if(total + len + i - j > L)
                    i--;
                else
                    total += len;
                    
                //format this line from j -> i
                String s = "";
                
                if(i==j)
                {
                    s = padRight(words[i], L-total);
                }
                else
                {
                    int total_space = L - total;
                    int sp = total_space / (i -j);
                    int rm = total_space % (i -j);
                    
                    for(int k=j; k<=i; k++)
                    {
                        s += words[k];
                        if(k==i)
                            break;
                        else if( k - j + 1 <= rm )
                            s = padRight(s, sp +1);
                        else
                            s = padRight(s, sp);
                    }
                }
                    
                list.add(s);
                
                i++;
                j = i;
                total = 0;
                
            }
            else
            {
                total += len;
                i++;
            }
        }
        
        //last line
        if(j<words.length)
        {
            String s ="";
            
            for(int k=j; k<words.length; k++)
            {
                s += words[k];
                if(k == words.length-1)
                    s = padRight(s, L - total - (words.length - j -1));
                else 
                    s = padRight(s, 1);
            } 
            
            list.add(s);
        }
        
        return list;
    }
    
    public String padRight(String s, int n)
    {
        StringBuilder sb = new StringBuilder(s);
        
        for(int i=0; i<n; i++)
            sb.append(' ');
            
        return sb.toString();
        
    }
    }

Log in to reply
 

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