# Share my concise solution, this is easy, should it classify to be hard ?

• ``````vector<string> fullJustify(vector<string> &words, int L) {
vector<string> ans, vs;
string str;
int len = 0, div = 0, mod = 0;

for (int i = 0; i < words.size(); ++i) {
if (len + vs.size() + words[i].size() <= L) {
vs.push_back(words[i]);
len += words[i].size();
}
else {
if (vs.size() == 1) {
str = vs[0];
str.append(L - str.size(), ' ');
ans.push_back(str);
}
else if (vs.size() > 1) {
div = (L - len) / (vs.size() - 1);
mod = (L - len) % (vs.size() - 1);
str = vs[0];
for (int j = 1; j < vs.size(); ++j) {
if (j <= mod) str.append(div+1, ' '); // one more space
else str.append(div, ' ');
str += vs[j];
}
ans.push_back(str);
}

vs.clear();
vs.push_back(words[i]);
len = words[i].size();
}
}

// left justified and no extra space is inserted between words
str = vs[0];
for (int i = 1; i < vs.size(); ++i) {
str += ' ' + vs[i];
}
str.append(L-str.size(), ' ');
ans.push_back(str);
return ans;
}``````

• Basically we go through the String array of words and check whether the length of this line + # of spaces + length of next word is bigger than L. If not, just add the word and update length. Otherwise, we build this line and append the word to next line.

Note the calculation of spaces between words. We divide the rest length of current line with the # of interval between words, which is line.size() - 1. # of spaces between words can be just quotient, or quotient + 1 if we still have remainder.

Here is my Java implementation of your idea.

``````public static List<String> fullJustify(String[] words, int L) {
List<String> res = new ArrayList<String>();
if (words == null || words.length == 0 || L < 0) return res;
List<String> line = new ArrayList<String>();
String str = "";
int len = 0, div, mod;
for (int i = 0; i < words.length; i++) {
if (len + line.size() + words[i].length() <= L) {
len += words[i].length();
} else {
if (line.size() == 1) { // only 1 word in this line
str = line.get(0);
for (int j = L - str.length(); j > 0; j--) str += " ";
} else if (line.size() > 1) {
div = (L - len) / (line.size() - 1);
mod = (L - len) % (line.size() - 1);
str = line.get(0); // append first word
for (int j = 1; j < line.size(); j++) { // append remaining words
for (int k = 0; k < div; k++) str += " ";
if (j <= mod) str += " "; // append 1 more space
str += line.get(j);
}
}
line.clear();