# Share my concise c++ solution - less than 20 lines

• ``````vector<string> fullJustify(vector<string> &words, int L) {
vector<string> res;
for(int i = 0, k, l; i < words.size(); i += k) {
for(k = l = 0; i + k < words.size() and l + words[i+k].size() <= L - k; k++) {
l += words[i+k].size();
}
string tmp = words[i];
for(int j = 0; j < k - 1; j++) {
if(i + k >= words.size()) tmp += " ";
else tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' ');
tmp += words[i+j+1];
}
tmp += string(L - tmp.size(), ' ');
res.push_back(tmp);
}
return res;
}
``````

For each line, I first figure out which words can fit in. According to the code, these words are words[i] through words[i+k-1]. Then spaces are added between the words. The trick here is to use mod operation to manage the spaces that can't be evenly distrubuted: the first (L-l) % (k-1) gaps acquire an additional space.

• Great solution. Thanks for sharing.

Here's a Java version:

``````public class Solution {
public List<String> fullJustify(String[] words, int L) {

for (int i = 0, w; i < words.length; i = w) {
int len = -1;
for (w = i; w < words.length && len + words[w].length() + 1 <= L; w++) {
len += words[w].length() + 1;
}

StringBuilder strBuilder = new StringBuilder(words[i]);
int space = 1, extra = 0;
if (w != i + 1 && w != words.length) { // not 1 char, not last line
space = (L - len) / (w - i - 1) + 1;
extra = (L - len) % (w - i - 1);
}
for (int j = i + 1; j < w; j++) {
for (int s = space; s > 0; s--) strBuilder.append(' ');
if (extra-- > 0) strBuilder.append(' ');
strBuilder.append(words[j]);
}
int strLen = L - strBuilder.length();
while (strLen-- > 0) strBuilder.append(' ');
}

return list;
}
}``````

• Thanks. (L-l) % (k-1) to add extra space is very brilliant.

• Hi, qddpx. Thanks for your sharing! Really brilliant codes! I think besides `(L - l) % (k - 1)` mentioned by mcrystal, `l + words[i+k].size() <= L - k` is also very clever since it unifies both cases of a single word multiple words (and thus spaces are required)

• The nice structure and variable names make the code easy to understand. BTW, `int len = -1;` is so clerver :-)

• ``````len = -1
``````

is really brilliant

• what are i,j,l,k meaning ? it's better make some comments.

``````public class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ret = new ArrayList<>();
if(words.length == 0 || maxWidth == 0) {
ret.add(""); //for some reason OJ expects list with empty string for empty array input
return ret;
}

for(int i = 0, w; i < words.length; i = w) {
int len = -1; //We need to skip the space for last word hence start len = -1
//check how many words fit into the line
for(w = i; w < words.length && len + words[w].length() + 1 <= maxWidth; w++) {
len += words[w].length() + 1; // 1 extra for the space
}

//calculate the number of extra spaces that can be equally distributed
//also calculate number of extra spaces that need to be added to first few
//words till we fill the line width
//For example line width is 20 we have three words of 3 4 2 4 length
//[our_,life_,is_,good_,_,_,_,_,] ==> [our_,_,_,life_,_,_is_,_,good]
//   Note _, indicates space
//Count number of empty spaces at end of line:= width-len = 20-(15) = 5
//These five spaces need to be equally distributed between 4-1 = 3 gaps
//n words will have n-1 gaps between them
// 5 / 3 = 1 extra space between each word (in addition to default 1 space,
//                                          total space count = 2)
// 5 % 3 = 2 extra spaces between first three words as shown above

int evenlyDistributedSpaces = 1; //If we don't enter loop at line # 37 then we need to have default value
int extraSpaces = 0;
int numOfGapsBwWords = w-i-1; //w is already ponting to next index and -1 since
//n words have n-1 gaps between them

//Moreover we don't need to do this computation if we reached the last word
//of array or there is only one word that can be accommodate on the line
//then we don't need to do any justify text. In both cases text can be left,
//left-aligned

if(w != i+1 && w != words.length) {
//additional 1 for the default one space between words
evenlyDistributedSpaces = ((maxWidth-len) / numOfGapsBwWords) + 1;
extraSpaces = (maxWidth-len)%numOfGapsBwWords;
}

StringBuilder sb = new StringBuilder(words[i]);
for(int j = i+1; j < w; j++) {
for(int s = 0; s < evenlyDistributedSpaces; s++) {
sb.append(' ');
}
if(extraSpaces > 0) {
sb.append(' ');
extraSpaces--;
}
sb.append(words[j]);
}

//Handle the above two cases we skipped, where there is only one word on line
//or we reached end of word array. Last line should remain left aligned.
int remaining = maxWidth-sb.length();
while(remaining > 0) {
sb.append(' ');
remaining--;
}
}
return ret;
}
}
``````

• @melvin.ming.gong The calculation of space and extra is a little confusing to me, so I made a slight change. Here is the variation with comments for your reference. Thanks for your sharing!

``````    //   0   1  2    3
// "This is an example..."
//  i=0, j=3, width=8, space=(16-8)/(3-0-1)=4, extra=0
// ------------------------------------------------------
//   3      4   5        6
// "example of text justification."
//  i=3, j=6, width=13, space=(16-13)/(3-0-1)=1, extra=1
// ------------------------------------------------------
// "justification."
//  i=6, j=7, space=1, extra=0
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
for (int i = 0, j; i < words.length; ) {
int width = 0;                                  // width of words without space
for (j = i; j < words.length && width + words[j].length() + (j - i) <= maxWidth; j++)
width += words[j].length();                 /* j is the next word */

int space = 1, extra = 0;                       // for last line, space=1
if (j - i != 1 && j != words.length) {          // not 1 word (div-by-zero) and not last line
space = (maxWidth - width) / (j - i - 1);   // minus 1 to exclude skip last word
extra = (maxWidth - width) % (j - i - 1);
}

StringBuilder line = new StringBuilder(words[i]);
for (i = i + 1; i < j; i++) {                   // move i to j finally
for (int s = space; s > 0; s--) line.append(" ");
if (extra-- > 0) line.append(" ");
line.append(words[i]);
}
for (int s = maxWidth - line.length(); s > 0; s--) line.append(" ");
}
return result;
}
``````

``````class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> result;
for(int i = 0, j; i < words.size(); i = j) {
int width = 0;
for(j = i; j < words.size() && width + words[j].size() + j - i <= maxWidth; j++) {
width += words[j].size();
}
int space = 1, extra = 0;
if(j - i != 1 && j != words.size()) {
space = (maxWidth - width) / (j - i - 1);
extra = (maxWidth - width) % (j - i - 1);
}
string line(words[i]);
for(int k = i + 1; k < j; k++) {
line += string(space, ' ');
if(extra-- > 0) {
line += " ";
}
line += words[k];
}

line += string(maxWidth - line.size(), ' ');
result.push_back(line);
}
return result;
}
};
``````

• As others have already applauded solution is very neat. Apart from that I have newly learnt that the operators && and || can be substituted now with "and" and "or" respectively. Wow!

• @G513 Do you know why it can be replaced using "and"? Is this a C++ thing?

• This question is actually not hard... But I didn't figure it out in a period of acceptable time.

Your solution is exactly the same as mine, but much more elegant, thanks for your sharing.

Below is the Java version with `comment`:

``````public List<String> fullJustify(String[] words, int L) {
List<String> res = new ArrayList();
for (int i = 0, k; i < words.length; i = k) {
// i: the index of word
// k: the current index of words in the line
// len: current total len of words in the line
int len = -1;
for (k = i; k < words.length && len + words[k].length() + 1 <= L; k++) {
len += words[k].length() + 1;
}
StringBuilder curStr = new StringBuilder(words[i]);
int space = 1, extra = 0;
// not 1 char, not last line
if (k != i + 1 && k != words.length) {
space = (L - len) / (k - i - 1) + 1; // 1 is for another space
extra = (L - len) % (k - i - 1);
}
// not 1 char, including last line, initialize space == 1 is to deal with last line case.
for (int j = i + 1; j < k; j++) { // j: index of word in the current line
for (int s = space; s > 0; s--) curStr.append(" "); // add the "even" space
if (extra-- > 0) curStr.append(" ");
curStr.append(words[j]);
}
// if it's the last line
int strLen = L - curStr.length();
while (strLen-- > 0) curStr.append(" ");
}
return res;
}
``````

• What an elegant solution!!! Good job!

• This line is wonderful
`tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' ');`

• One more solution that is concise and straightforward.
pre-allocate string with all space.

``````vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> res;
for (int i = 0, sz = words.size(); i < sz;) {
int cnt = words[i].size();
int j = i;
for (++i; i < sz && cnt + words[i].size() + 1 <= maxWidth; ++i) { cnt += words[i].size() + 1; }
string s (maxWidth, ' ');
int n_space = 1, one_more = 0;
if (i != sz && i - j > 1) n_space = 1 + (maxWidth - cnt) / (i - j - 1), one_more = (maxWidth - cnt) % (i - j - 1);
auto p = s.begin();
for (; j < i; ++j) {
for (auto ch: words[j]) { *p++ = ch; }
p += n_space + (one_more-- > 0);
}
res.push_back(std::move(s));
}
return res;
}``````

• @JadenPan can you tell me tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' '); that (j < (L - l) % (k - 1) is what meaning? Thank you.

• @Tomecs since there are k words,that means there are k-1 slots and the extra characters are (total length of line)-total no of characters in all the words in that line) which is nothing but L-l and k-1 here refers to total slots as there are k words,
for example,consider the below case,
<word>....<word>.....<word>....<word> and there are 8 extra characters,how would you distribute them...?
<word> 1st extra char <word> 2nd extra char <word> 3rd..<word>
<word> 4th..<word> 5th..<word> 6th <word>
<word> 7th <word> 8th......right..?
which is nothing but l-l/k-1 for words greater than 8%3=2;

• https://discuss.leetcode.com/topic/110789/missing-test-case
All the solutions in the most upvoted post can't pass this missing test case

Input:
["a","b","c","d"]
3
Output:
["a b","c d"]

This output violates the following description:

For the last line of text, it should be left justified and no extra space is inserted between words.

What's the right answer for this test case?

• Similarly, here's my Java Code

``````        public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
if (words == null || words.length == 0 || maxWidth < 0) return res;
int n = words.length;
int s = 0, e = 0;
for (s = 0; s < n; s = e) {
int len = -1;
for (e = s; e < n && len + words[e].length() + 1 <= maxWidth; ++e) {
len += words[e].length() + 1;
}
int space = 1;
int extra = 0;
if (e != s + 1 && e != n) {
space = (maxWidth - len) / (e - s - 1) + 1;
extra = (maxWidth - len) % (e - s - 1);
}
StringBuilder row = new StringBuilder(words[s]);
for (int i = s + 1; i < e; ++i) {
if (--extra >= 0) row.append(' ');
row.append(words[i]);
}