Text justification

Hard TimeO(n) SpaceO(n)

Given an array of words and a line width, lay the words out into lines that are each exactly width characters, and return them. A line takes as many words as fit, counting the single space that must separate each pair. The spaces left over are shared across the gaps, with the leftmost gaps taking the extra when they do not divide evenly. The last line is the exception: it is left-aligned with single spaces and padded on the right.

Examples

Example 1

Input

words = ["This", "is", "an", "example", "of", "text", "justification."]width = 16

Output

This    is    an
example  of text
justification.

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

Line 1 shares 8 spare spaces evenly over 2 gaps; line 2 has 3 over 2, so the left gap takes the extra; the last line is left-aligned.

Example 2

Input

words = ["justification.", "is", "hard"]width = 14

Output

justification.
is hard

["justification.","is hard "]

One word fills the first line exactly, so there is no gap to spread; the last line is left-aligned and padded.

The Code

function fullJustify(words, width) {
  const lines = [];
  let i = 0;
  while (i < words.length) {
    let last = i;
    let letters = 0;
    while (last < words.length && letters + words[last].length + (last - i) <= width) {
      letters += words[last].length;
      last++;
    }
    const count = last - i;
    const gaps = count - 1;
    let line = "";
    if (gaps === 0 || last === words.length) {
      for (let w = i; w < last; w++) {
        line += words[w];
        if (w < last - 1) line += " ";
      }
      while (line.length < width) line += " ";
    } else {
      const base = Math.floor((width - letters) / gaps);
      const extra = (width - letters) % gaps;
      for (let w = i; w < last; w++) {
        line += words[w];
        if (w === last - 1) break;
        const pad = base + (w - i < extra ? 1 : 0);
        for (let p = 0; p < pad; p++) line += " ";
      }
    }
    lines.push(line);
    i = last;
  }
  return lines;
}
fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16);

Done

The first 23 calls, of 43. This one does not fit on a page.

Step through fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16) call by call

More like this

All strings examples (13) →