The key to this problem is to identify all the words that can be added to a line and then identify the places that require an additional space (to make the spaces as even as possible, we can only add an additional space if needed). This link has a brilliant solution that has a nice formula for the places that require an addtional space. The code is written as follows.
1 class Solution { 2 public: 3 vector<string> fullJustify(vector<string>& words, int maxWidth) { 4 int idx = 0, n = words.size(); 5 vector<string> justifications; 6 while (idx < n) { 7 int width = 0, numWords = 0; 8 while (idx + numWords < n && width + words[idx + numWords].length() <= maxWidth - numWords) { 9 width += words[idx + numWords].length(); 10 numWords++; 11 } 12 string justification = words[idx]; 13 for (int j = 0; j < numWords - 1; j++) { 14 if (idx + numWords == n) justification += " "; 15 else justification += string((maxWidth - width) / (numWords - 1) + (j < (maxWidth - width) % (numWords - 1)), ' '); 16 justification += words[idx + j + 1]; 17 } 18 justification += string(maxWidth - justification.length(), ' '); 19 justifications.push_back(justification); 20 idx += numWords; 21 } 22 return justifications; 23 } 24 };
