My easy-understand C++ solution


  • 0

    This problem looks like a function rather than algorithm. Note that when a line has only one word, this line should be left justified and complement this line with space.

    vector<string> fullJustify(vector<string>& w, int l) 
    {
    	vector<string> ret;
    	if (w.empty())
    		return ret;
    	int i, j, curl = 0, count, space, re; //curl: current words' length (except space), count: word number, space: space length, re: remainder
    	string st;
    	int ws = w.size();
    	for (i = 0; i < ws;)
    	{
    		j = i;
    		curl = w[j].size();
    		count = 1;
    		for (; j + 1 < ws && curl + w[j + 1].size() + count <= l;)
    		{
    			++j, ++count;
    			curl += w[j].size(); 
    		}
    		if (ws - 1 == j) //in the last line
    		{
    			for (i; i <= j; ++i)
    			{
    				st += w[i];
    				if (i != j)
    					st += " ";
    			}
    			string t(l - st.size(), 32);
    			st += t;
    			ret.push_back(st);
    			break;
    		}
    		if (i == j || ws - 1 == j) //there is only one word is allowed in a line
    		{
    			st += w[i];
    			string t(l - w[i].size(), 32);
    			st += t;
    			++i;
    		}
    		else
    		{
    			space = (l - curl) / (count - 1);
    			re = (l - curl) % (count - 1);
    			string t(space, 32);
    			for (i; i <= j; ++i)
    			{
    				st += w[i];
    				if (i != j)
    				{
    					st += t;
    					if (re > 0)
    					{
    						st += " ";
    						--re;
    					}
    				}
    			}
    		}
    		ret.push_back(st);
    		st.clear(); //clean the temporary string 'st'.
    	}
    	return ret;
    }

Log in to reply
 

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