I have an Accepted C++ code to share


  • 0
    A
        void process(vector<string> &words, vector<string>&result, int start, int end, int L) {
        int size = 0;
        // end of the setence, left justification
        if(end==words.size()-1 ) {
            string s;
            int last_space = L;
            for(int i=start; i<=end; i++) {
                last_space-=words[i].size();
                s+=words[i];
                if(i!=end) {
                    s+= " ";
                    last_space--;
                }else {
                    s+= string(last_space, ' ');
                }
            }
            result.push_back(s); return;
        }
        // find the total size of the words
        for(int i=start; i<=end; i++) {
            size+=words[i].size();
        }
        // find the total space size
        int space = L-size;
        // if it's just one word, left justification
        if(start==end) {
            string s = words[start];
            s+= string((L-size), ' ');
            result.push_back(s); return;
        }
        // get the average space - n words needs (n-1) consecutive space
        int e_space = space/(end-start);
        // get the leftover space for the first kth words
        int n=space-e_space*(end-start);
        string s;
        for(int i=start; i<=end; i++) {
            s+= words[i];                       // word
            if(i!=end) s+=string(e_space, ' '); // space
            if((n--)>0) s+=string(1, ' ');      // additional space if any
        }
        result.push_back(s);
    }
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> result;
        if (L<0) return result;
        if(words.size()==0) return result;
        int start = 0; int sofar = 0;
        for(int i=0; i<words.size(); i++) {
            if(i+1<words.size() && (sofar+words[i].size()+words[i+1].size()<L)) {
                sofar = sofar+ words[i].size()+1;
            }else{
                process(words, result, start, i, L);
                start = i+1; sofar = 0;
            }
        }
    
        return result;
    }

  • 0
    R

    I have a java solution to share.

    The key part for this question is to use proper supporting methods. I have three supporting methods:buildWord(), which is build the normal line. buildLastLine(),which is quite self explainatary
    and allocate space. which is to distribute extra spaces among words.

    public class Solution {
    	int current=0;
    	List<String> list;
        public List<String> fullJustify(String[] words, int L) {
        	List<String> results = new LinkedList<String>();
            if (words==null||words.length==0) return  results;
            
            list = new LinkedList<String>();
            
            for (String s:words){     	
            	if ((current+list.size()+next)>L)
            		results.add(buildWord(list,L));
            	 list.add(s);	
            	 current+=s.length();
            }
    //Be careful about the last line.
    
            if (list.size()==1)
            	results.add(buildWord(list,L));
            else if (list.size()>1)
            	results.add(buildLastLine(list,L));
            return results;
        
        
        private String buildWord(List<String> l,int L){
        	StringBuilder sb = new StringBuilder();
        	for (int num=0;num<l.size();num++){
        		sb.append(l.get(num));
        		for (int i=0;i<allocateSpace(L-current,l.size()-1,num+1);i++)
        			sb.append(" ");
        	}
        	list.clear();
        	current=0;
        	return sb.toString();
        }
        private String buildLastLine(List<String> l,int L){
        	StringBuilder sb = new StringBuilder();
        	for (int num=0;num<l.size()-1;num++){
        		sb.append(l.get(num));
        		sb.append(" ");
        	}
        	sb.append(l.get(l.size()-1));
        	while(sb.length()<L) sb.append(" ");
        	return sb.toString();
        }
        private int allocateSpace(int space,int slots,int index){
        	if (slots==0) return space;
        	if (index>slots) return 0;
        	int result=space/slots;
        	result+=(index<=space%slots)?1:0;
        	return result;
        }   
    }

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0

    Thanks for the sharing. I'm confused about the line 'current+list.size()+next". Where the "next" is coming from?


  • 0
    J

    My readable code:

    class Solution {
    public:
        vector<string> fullJustify(vector<string> &words, int L) {
            if (words.size() < 0) return {};
            if (words.size() == 1) return {lastLine(words, 0, 1, L)};
            vector<string> result;
            int begin = 0;
            int sum = 0;
            for (int i = 0; i < words.size(); i++) {
                sum += words[i].length();
                if (i + 1 == words.size()) {
                    result.push_back(lastLine(words, begin, i + 1, L));
                } else if (sum + words[i+1].length() + (i + 1 - begin) > L) {
                    result.push_back(newLine(words, begin, i + 1, L, sum));
                    begin = i + 1;
                    sum = 0;
                }
            }
            return result;
        }
        string newLine(vector<string> &words, int begin, int end, int max, int sum) {
            if (end - begin == 1) {
                return words[begin] + string(max - words[begin].length(), ' ');
            }
            int n = end - begin;
            int allSpace = max - sum;
            int extraSpace = allSpace % (n - 1);
            int spaceLength = allSpace / (n - 1);
            string line;
            string padding(spaceLength, ' ');
            for (int i = begin; i < end; i++) {
                line += words[i];
                if (i < end - 1) {
                    line += padding;
                    if (extraSpace > 0) {
                        line += ' ';
                        extraSpace--;
                    }
                }
            }
            return line;
        }
        string lastLine(vector<string> &words, int begin, int end, int length) {
            string line(length, ' ');
            int pos = 0;
            for (int i = begin; i < end; i++) {
                line.replace(pos, words[i].length(), words[i]);
                pos += words[i].length() + 1;
            }
            return line;
        }
    };

Log in to reply
 

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