Text Justification Hard 0 attempts
LeetCode ↗

Text Justification

Hard StringHash Table LeetCode

Given a list of words and a target line width maxWidth, lay the words out into lines so each line (except possibly the last) is padded with spaces to be exactly maxWidth characters wide, with extra spaces distributed as evenly as possible between words. Pack each line greedily; when spaces do not divide evenly, give the leftmost gaps one extra space. The last line and any single-word line are left-aligned with trailing spaces, and every line must be exactly maxWidth characters long.

Input Format
Implement fullJustify(words, maxWidth). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
words = ["This","is","an","example","of","text","justification."]
maxWidth = 16
Output
["This    is    an","example  of text","justification.  "]

Example 2

Input
words = ["a"]
maxWidth = 3
Output
["a  "]
Constraints
  • 1 <= words.length <= 300
  • 1 <= maxWidth <= 100
  • 1 <= words[i].length <= min(20,maxWidth)
  • Words contain no spaces.
Test Cases (2)
Case 1
Args: [["This","is","an","example","of","text","justification."],16] Expected: ["This is an","example of text","justification. "]
Case 2
Args: [["a"],3] Expected: ["a "]
Topics
StringHash Table

Greedy Line Packing + Space Distribution

javascript
function fullJustify(words, maxWidth) {
  const result = [];
  let i = 0;
  while (i < words.length) {
    let j = i, lineLen = 0;
    while (j < words.length && lineLen + words[j].length + (j-i) <= maxWidth) lineLen += words[j++].length;
    const numWords = j - i, numSpaces = maxWidth - lineLen;
    let line = words[i];
    if (numWords === 1 || j === words.length) {
      for (let k = i+1; k < j; k++) line += ' ' + words[k];
      line += ' '.repeat(maxWidth - line.length);
    } else {
      const gaps = numWords - 1, spacePerGap = Math.floor(numSpaces / gaps), extra = numSpaces % gaps;
      for (let k = 1; k < numWords; k++) line += ' '.repeat(spacePerGap + (k <= extra ? 1 : 0)) + words[i+k];
    }
    result.push(line); i = j;
  }
  return result;
}

Time: O(C + W), where C is total input characters and W is total output characters | Space: O(W), including output

Saved in this browser only. Private to you.

JavaScript