C++ solution with explanation


  • 0
    Z

    First we need to decide how many strings will be put in one line.
    There are three possibilities for each line:

    1. only one string;
    2. more than one string, and the line is not the last line;
    3. more than one string, and the line is the last line.

    They will be processed separately.

    class Solution {
    public:
        vector<string> fullJustify(vector<string>& words, int maxWidth) {
            vector<string> vec;
            
            justified(words,maxWidth,vec);
            return vec;
        }
        
        void justified(vector<string>& words, int maxWidth, vector<string>& vec){
            if(words.size()==1){
                string str = words[0];
                words.erase(words.begin());
                while(str.size()<maxWidth){
                    str = str + " ";
                }
                vec.push_back(str);
                return;
            }
            
            string str_temp;
            str_temp = words[0];
            int width=str_temp.size();
            int number_of_word=1;
            int i = 1;
            
            while(i<words.size() && width+words[i].size()+1<=maxWidth){
                width=width+words[i].size()+1;
                number_of_word++;
                i++;
            }
            
            if(number_of_word==1){
                while(str_temp.size()<maxWidth){
                    str_temp = str_temp +" ";
                }
                vec.push_back(str_temp);
                words.erase(words.begin());
                return justified(words, maxWidth, vec);
            }
            else if(number_of_word==words.size()){
                words.erase(words.begin());
                for(int m=1; m<number_of_word; m++){
                    str_temp=str_temp+" "+words[0];
                    words.erase(words.begin());
                }
                while(str_temp.size()<maxWidth){
                    str_temp = str_temp +" ";
                }
                vec.push_back(str_temp);
                return;
            }
            else{
                int space = (maxWidth-width)/(number_of_word-1)+1;
                int left = (maxWidth-width)%(number_of_word-1);
                words.erase(words.begin());
                for(int j=1; j<number_of_word; j++){
                    if(j<=left){
                        for(int k=0;k<space+1; k++){
                            str_temp=str_temp+" ";
                        }
                        str_temp=str_temp+words[0];
                        words.erase(words.begin());
                    }
                    else{
                        for(int l=0;l<space; l++){
                            str_temp=str_temp+" ";
                        }
                        str_temp=str_temp+words[0];
                        words.erase(words.begin());
                    }
                }
                vec.push_back(str_temp);
                return justified(words, maxWidth, vec);
            }
            
        }
    };
    

Log in to reply
 

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