68.text-justification.js

/*
 * @lc app=leetcode id=68 lang=javascript
 *
 * [68] Text Justification
 *
 * https://leetcode.com/problems/text-justification/description/
 *
 * algorithms
 * Hard (21.88%)
 * Total Accepted:    85.2K
 * Total Submissions: 389.4K
 * Testcase Example:  '["This", "is", "an", "example", "of", "text", "justification."]\n16'
 *
 * Given an array of words and a width maxWidth, format the text such that each
 * line has exactly maxWidth 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 maxWidth characters.
 *
 * 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.
 *
 * Note:
 *
 *
 * A word is defined as a character sequence consisting of non-space characters
 * only.
 * Each word's length is guaranteed to be greater than 0 and not exceed
 * maxWidth.
 * The input array words contains at least one word.
 *
 *
 * Example 1:
 *
 *
 * Input:
 * words = ["This", "is", "an", "example", "of", "text", "justification."]
 * maxWidth = 16
 * Output:
 * [
 * "This    is    an",
 * "example  of text",
 * "justification.  "
 * ]
 *
 *
 * Example 2:
 *
 *
 * Input:
 * words = ["What","must","be","acknowledgment","shall","be"]
 * maxWidth = 16
 * Output:
 * [
 * "What   must   be",
 * "acknowledgment  ",
 * "shall be        "
 * ]
 * Explanation: Note that the last line is "shall be    " instead of "shall
 * be",
 * because the last line must be left-justified instead of fully-justified.
 * ⁠            Note that the second line is also left-justified becase it
 * contains only one word.
 *
 *
 * Example 3:
 *
 *
 * Input:
 * words =
 * ["Science","is","what","we","understand","well","enough","to","explain",
 * "to","a","computer.","Art","is","everything","else","we","do"]
 * maxWidth = 20
 * Output:
 * [
 * "Science  is  what we",
 * ⁠ "understand      well",
 * "enough to explain to",
 * "a  computer.  Art is",
 * "everything  else  we",
 * "do                  "
 * ]
 *
 *
 */
/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
var fullJustify = function(words, maxWidth) {
  const wordInLines = [], spacesInLines = [];

  let line = [], charCnt = 0;
  for (let word of words) {
    if (charCnt + line.length - 1 + word.length >= maxWidth) {
      if (line.length === 1) line.push('');
      wordInLines.push(line);
      spacesInLines.push(maxWidth - charCnt);
      line = [];
      charCnt = 0;
    }

    line.push(word);
    charCnt += word.length;
  }
  const lastLine = line;
  const lastLineSpaces = maxWidth - charCnt;

  return [
    ...wordInLines.map((words, i) => {
      const spaces = Math.floor(spacesInLines[i] / (words.length - 1));
      let remainSpaces = spacesInLines[i] % (words.length - 1);

      return words.reduce((p, word, i) => {
        p += `${' '.repeat(spaces)}${remainSpaces-- > 0 ? ' ' : ''}${word}`;
        return p;
      });
    }),
    lastLine.join(' ') + ' '.repeat(lastLineSpaces - (lastLine.length - 1)),
  ];
};