Leetcode # 68. Text Justification

Problem

https://leetcode.com/problems/text-justification

Solution

Time Complexity: O(len(words))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
    result = []
    i = 0
    n = len(words)
    while i < n:
      result.append(words[i])
      j = i
      l = len(result[-1])
      while j < n - 1:
        if l + len(words[j + 1]) + 1 > maxWidth:
          break
        l += (len(words[j + 1]) + 1) if j < n - 1 else 0
        j += 1
      if j == n - 1 or i == j:
        for k in range(i + 1, j + 1):
          result[-1] += " " * 1 + words[k]
        result[-1] = result[-1].ljust(maxWidth)
      else:
        gap_n = j - i
        space_n = 1 + (maxWidth - l) // gap_n
        remained_space_n = maxWidth - gap_n * (space_n - 1) - l
        for k in range(i + 1, j + 1):
          result[-1] += " " * space_n + (" " if remained_space_n > 0 else "") + words[k]
          remained_space_n -= 1
      i = j + 1
    return result

Last Updated on 2023/08/24 by A1go