Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

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

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Solution:

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

This is straight forward implementation. Two pointers to point to the start and end of a line.

Count the length of a line first, then form a line.

My first attempt is to form a line then add extra space, and this is too complicated.

Code:

vector fullJustify(vector &words, int L) {

            vector result;

            if(0 == words.size()) return result;

            int i =0;

            while(i< words.size())

            {

                 int start = i;

                 int sum = 0;

                 while(i

                 {

                      sum+=words[i].size() +1;  // 1 for one space

                      i++;

                 }

                 int ed = i-1;

                 int intervalCount = ed - start;

                 int avgSp = 0, leftSp = 0;

                 if(intervalCount >0)

                 {

                      avgSp = (L-sum + intervalCount+1)/intervalCount;

                      leftSp = (L-sum + intervalCount+1)%intervalCount;

                 }

                 string line;

                 for(int j = start; j

                 {

                      line+=words[j];

                      if(i == words.size()) // the last line

                         line.append(1, ' ');

                      else

                      {

                           line.append(avgSp, ' '); //average space

                           if(leftSp>0) // the extra space

                           {

                            line.append(1, ' ');

                            leftSp--;

                           }

                      }

                 }

                 line+=words[ed];

                 if(line.size()

                      line.append(L-line.size(), ' ');

                 result.push_back(line);

            }

        return result;

}