leetcode Question 110: Text Justification

Test Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. 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.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

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

Note: Each word is guaranteed not to exceed L in length.

Corner Cases:

• A line other than the last line might contain only one word. What should you do in this case?
  In this case, that line should be left-justified.

Analysis:

The idea of my solution is not efficient, but easily understood.
It is easier to follow the Python code below.

Step 1: Find the level number for each word. Assuming that there is at least 1 space between two words.
Step 2: Find the number of word in each level and the total spaces needed in that level.
Step 3: Compute the number of spaces M in each level that is needed between two words. If the spaces are not evenly distributed. Compute the number of words where 1+M spaces is needed, and the between the rest of words there needed M spaces.
Step 4: Write the levels which has only one word to the result.
Step 5: Find the levels that the last word that level ends with '.' (which is the sentence end).
Step 6: Write the levels to the result.
Step 7: Return result.

Code(Python):

class Solution:
    # @param words, a list of strings
    # @param L, an integer
    # @return a list of strings
    def fullJustify(self, words, L):
        
        lens = 0    # word length + single space in current level
        result = [] # result list of strings
        single_level = [] # list of strings in current level
        
        for word in words:
            lens += len(word)   
            if lens <= L:   
                single_level.append(word)   # add word into current level
                lens += 1   # add single space length
            else: #if word cannot be in current level
            
                #get result string add to final results
                result.append(self.proc_sinlge_lev(single_level, L, False))
                #refresh the current level
                single_level = []
                single_level.append(word)
                lens = len(word) + 1
                
        #handle the last level of words
        result.append(self.proc_sinlge_lev(single_level, L, True))
        #return final result
        return result
        
    
    # @param single_level, a list of strings 
    # @param L, an integer
    # @param last, an bool (True if current level is the last level)
    def proc_sinlge_lev(self,single_level, L, last):
        
        #last level no extra spaces inserted
        if last == True:
            if len(single_level) == 1:  #only 1 word in current level
                str_lev = single_level[0].ljust(L)
            else:
                str_lev = ""  #result string
                for str in single_level[0:-1]:
                    str_lev += str.ljust(len(str)+1) # 1 is a single space
                str_lev += single_level[-1] # add the last word
                str_lev = str_lev.ljust(L) # fill out spaces
            return str_lev
        else:
            # compute lens of this level
            if len(single_level) == 1: # only 1 word in current level
                str_lev = single_level[0].ljust(L)
            else:
                lev_len = sum(len(s) for s in single_level) # sum of word length in current level
                sp = L-lev_len  # total space numbers 
                first = sp % (len(single_level)-1)  # how many spaces needed when the spaces can not be evenly divided
                sp_s = sp / (len(single_level)-1) # how many spaces are needed between two words
                str_lev ="" # result string
                for str in single_level[0:-1]:
                    if first != 0:  # add one more spaces from the left 
                        str_lev += str.ljust(len(str)+sp_s+1)
                        first -=1
                    else:
                        str_lev += str.ljust(len(str)+sp_s)
                        
                str_lev += single_level[-1] #add last word
                
            return str_lev
            
            
        
            
            
                
             

Code(C++):

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> res;
        vector<int> lev;
         
        int len=0;
        int l=0;
         
        for (int i=0;i<words.size();i++){
            len +=words[i].size();
            if (len<=L){lev.push_back(l);len++;}
            else{l++; lev.push_back(l);len=words[i].size()+1;}
        }
         
        lev.push_back(-1);
         
        vector<int> sp(l+1,L);
        vector<int> sp_mode(l+1,0);
        vector<int> nword(l+1,0);
        for (int i=0;i<words.size();i++){
            sp[lev[i]] -= words[i].size();
            ++nword[lev[i]];
        }
         
        for (int i=0;i<=l;i++){
            if (nword[i]>1){
                sp_mode[i] = sp[i]%(nword[i]-1);
                sp[i] = sp[i]/(nword[i]-1);
            }
        }
         
         
        res=vector<string>(l+1,"");        
        for (int i=0;i<words.size();i++){
            if (nword[lev[i]]==1){
                res[lev[i]] += words[i];
                res[lev[i]] += string(sp[lev[i]],' ');
                nword[lev[i]]=0;
            }
        }
         
         
         
        vector<bool> flag(l+1,false);
         
        int prev=-1;
        for (int i=0;i<words.size();i++){
            if (nword[lev[i]]>0){
                if (lev[i+1]!=lev[i]){
                    if (words[i][words[i].size()-1]=='.') {
                        if (prev==-1){
                            prev = i;    
                        }else{
                            flag[lev[prev]]=false;    
                            prev = i;
                        }
                        flag[lev[i]]=true;
                    }
                }
            }
        }
         
         
        for (int i=0;i<words.size();i++){
             
            if (nword[lev[i]]>0){
                 
                if (flag[lev[i]]==true){
                    res[lev[i]] += words[i];
                    nword[lev[i]]--;
                    if (nword[lev[i]]>0){
                        res[lev[i]]+=' ';
                    }else{
                        res[lev[i]]+=string(L-res[lev[i]].size(),' ');
                    }
                }else{
                 
                res[lev[i]] += words[i];
                nword[lev[i]]--;
                             
                if (nword[lev[i]]>0){
                    if (sp_mode[lev[i]]>0){
                        res[lev[i]] += string(sp[lev[i]]+1,' ');
                        sp_mode[lev[i]]--;
                    }else{
                        res[lev[i]] += string(sp[lev[i]],' ');
                    }   
                }
                }
            }
        }
         
        return res;
    }
};