One Pager Cheat Sheet

• We can achieve a more balanced text layout by evenly distributing spaces between all words on each line, while fitting as many words as possible, in O(n^2) time, using O(n) space complexity.
• Our goal is to minimize the cost of text justification by finding the arrangement of words with the least amount of extra spaces between them.
• Dynamic programming can be used to divide a text justification problem into sub-problems, each with a recursive sub-structure, and an overall cost function can be found using f(i,j) and DP[i] to determine the optimal word boundary for each line with split[i].
• The DP and split arrays can be computed using an optimized for loop pseudo-code algorithm.
• We can determine the lines of text in our solution by tracking the index of the last word in each line using a list called lineEnd and then justifying the text by inserting the right amount of spaces between words.
• The time complexity is O(n$^2$) and the **space complexity** isO(n)` for the dynamic programming solution of the text justification problem.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function textJustification(words, maxWidth) {

  const res = [[]];

  res[0].letters = 0;

  for (let word of words) {

    let row = res[res.length - 1];

    if (row.length && row.letters + row.length + word.length > maxWidth) {

      res.push([]);

      row = res[res.length - 1];

      row.letters = 0;

    }

    row.push(word);

    row.letters += word.length;

  }

  for (let r = 0; r < res.length; r++) {

    let row = res[r];

    if (row.length === 1 || r === res.length - 1) {

      res[r] =

        row.join(' ') + ' '.repeat(maxWidth - row.letters - row.length + 1);

      continue;

    }

    let line = row[0];

    let spaces = maxWidth - row.letters;

    let minSpaces = ' '.repeat(Math.floor(spaces / (row.length - 1)));

    let addSpace = spaces % (row.length - 1);

    for (let w = 1; w < row.length; w++) {

      line += minSpaces + (w <= addSpace ? ' ' : '') + row[w];

    }

    res[r] = line;

  }

  return res.join('\n');

That's all we've got! Let's move on to the next tutorial.

If you had any problems with this tutorial, check out the main forum thread here.