Easy Java solution with comments


  • 0
    D
    public class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            
            //variable to store the answer
            List<String> solution=new ArrayList<String>();
            
            //Base case: if words is nul
            if(words==null)
                	return solution;
            
            //Base case: if maxWidth is 0, return an empty string
            if(maxWidth==0)
            {
                solution.add("");
                return solution;
            }
            
            //General case: if words is not null, and maxWidth is more than 0
            //to specify the start and end indices of the words which will be in the current Line
            int start_index=0;
            int end_index=-1;
            
            int current_index=0;
            
            //to keep track of length of words in current line
            int currentLineLength=0;
            
            //while loop to iterate through the array
            while(current_index<words.length)
            {
                //Case 1: if more words can fit in the line
                if(currentLineLength+words[current_index].length()<=maxWidth)
                {
                    currentLineLength+=words[current_index++].length()+1;
                    continue;
                }
                //Case 2:if capacity of a line is reached
                //mark the end index and call the function to form the string of the solution
                else
                {
                    end_index=current_index-1;
                    
                    formSolution(solution,words,maxWidth,start_index,end_index);
                       
                }
                
                //update start index and current line length
                start_index=current_index;
                currentLineLength=0;
            }
            
            //to form the last line
            StringBuilder lastLine=new StringBuilder();
            
            for(int i=start_index;i<words.length;i++)
            {
                lastLine.append(words[i]);
                
                if(i==words.length-1)
                {
                    int lastSpaces=maxWidth-lastLine.length();
                    
                    while(lastSpaces-->0)
                        lastLine.append(" ");
                    
                    break;
                }
                
                lastLine.append(" ");
            }
            
          
            solution.add(lastLine.toString());    
            
            return solution;
        }
        
        
        //function to form newly padded string and append to solution
        public void formSolution(List<String> solution, String[] words, int maxWidth, int start_index, int end_index)
        {
            int remainingLength=0;
            StringBuilder str=new StringBuilder();
            
            //Case 1:if only word is being appended
            if(start_index==end_index)
            {
                remainingLength=maxWidth-words[start_index].length();
                
                str.append(words[start_index]);
                
                while(remainingLength-->0)
                    str.append(" ");
            }
            
            //Case 2:if multiple words are being appended
            else
            {
                int wordSpaces=0;
                
                for(int i=start_index;i<=end_index;i++)
                    wordSpaces+=words[i].length();
                
                int emptySpaces=maxWidth-wordSpaces;
                
                int numWords=end_index-start_index;
                
                int spacesBetweenWords=-1;
                int copy_spacesBetweenWords=-1;
                
                for(int i=start_index;i<=end_index;i++)
                {
                    str.append(words[i]);
                    
                    //if current index is pointing to last word, break
                    if(i==end_index)
                        break;
                    
                    //Case 1:if number of spaces to divide among words is even
                    if((emptySpaces%numWords)==0)
                    {
                        spacesBetweenWords=emptySpaces/numWords;
                        
                        copy_spacesBetweenWords=spacesBetweenWords;
                        while(copy_spacesBetweenWords-->0)
                            str.append(" ");
                    }
                    //Case 2:if number of spaces to divide among words is odd
                    else
                    {
                        spacesBetweenWords=(emptySpaces/numWords)+1;
                        
                        copy_spacesBetweenWords=spacesBetweenWords;
                        
                        while(copy_spacesBetweenWords-->0)
                            str.append(" ");
                    }
                    
                    //update # of empty spaces left and number of words
                    emptySpaces=emptySpaces-spacesBetweenWords;
                    numWords--;
                }
                
                
            }
            
            
            //add the newly formed padded string to the solution
            solution.add(str.toString());
        }
    }
    

Log in to reply
 

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