Sharing my C++ solution using two functions. (Left Justified and Center Justified)


  • 0

    The basic idea is use two functions:

    1. Build line center justified
    2. Build line left justified

    Case A, Lines with more than 1 word and it is not the last line. Call (1) center justified.
    Case B, Lines with only 1 word and it is not the last line. Call (2) left justified.
    Case C, Last line of the result. Call (2) left justified.

    Codes are below:

    class Solution {
    public:
    	vector<string> fullJustify(vector<string> &words, int L) {
    		vector<string> result;
    		int lastIndex = words.size() - 1;
    		
    		int len = 0, count = 0, startIndex = 0;
    		for (int i = 0; i <= lastIndex; i++) {
    			len += words[i].length();
    			count++;
    			int line = len + count - 1;
    			
    			//Case C: Build last line:
    			if (line <= L && i == lastIndex) {
    				result.push_back(buildLineLeftJustified(words, startIndex, lastIndex, L));
    				break;				//END the loop and return result.
    			}
    			
    			//Case B: Build line with only one word.
    			if (line > L && i - startIndex == 1) {
    				result.push_back(buildLineLeftJustified(words, startIndex, startIndex, L));
    				startIndex = i; len = 0; count = 0; i--; //Reset the value and continue to the next loop.
    				continue;			
    			}
    			
    			//Case A: Build line with more than one word.
    			if (line > L && i - startIndex > 1) {
    				len -= words[i].length(); count--;
    				result.push_back(buildLineCenterJustified(words, startIndex, i-1, L, len, count));
    				startIndex = i; len = 0; count = 0; i--; //Reset the value and continue to the next loop.
    				continue;			
    			}
    		}
    		
    		return result;
    	}
    	
    private:
    	string buildLineLeftJustified(vector<string> &words, int start, int end, int L) {
    		string str;
    		for (int i = start; i <= end; i++) {
    			str += words[i];
    			if (str.length() < L) str += " ";
    		}
    		while (str.length() < L) str += " ";
    		return str;
    	}
    	
    	string buildLineCenterJustified(vector<string> &words, int start, int end, int L, int len, int count) {
    		string str;
    		int avg = (L - (len + count - 1)) / (count - 1);		//calculate how many " " to add for each word
    		int extra = (L - (len + count - 1)) % (count - 1);	//calculate the reaming " " to add for each word.
    		
    		for (int i = start; i <= end; i++) {
    			str += words[i];
    			if (i == end) break;						//If last word, exit without padding.
    			
    			for (int j = 0; j <= avg; j++) str += " ";
    			
    			if (extra > 0) {						
    			    str += " ";
    			    extra--;
    			}
    		}
    		
    		return str;
    	}

Log in to reply
 

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