Text Justification | LeetCode | InterviewBit | Solution Explained
Text Justification LeetCode/Justified Text InterviewBit is a interesting problem. I use raw logic to explain the solution in detail. Problem Links: LeetCode 68. Text Justification InterviewBit Justified Text.
0. Text Justification: Problem Discussion
0.0. IO Format
- inputs: words (a list of words), maxWidth (max width of a sentence)
- output: list of strings of each maxWidth length
- pack as many words in the line as possible
- add spaces to evenly space out the words
- number of spaces must be the same between words
- (add remaining spaces to the left) #left_spaces >= #right_spaces
- last row is left justified
The constraints are a bit tricky to understand, so let’s take an example.
The answer in this case is given as such:
- We see that we can efficiently pack “this” “is” and “an” in the first row, but we can’t fit “example”, even with 1 spacing. So, we just have the first 3 words and space them out equally.
- Since “example” was sent to the second row, we start with that. We are able to add “of” and “text” too, but not “justification”. We then add the appropriate spaces between. Since there are 3 total spaces, we give left space one more than right.
- finally, last row is simply left justified.
1. Text Justification: Observations & Logic
This question is amazing. It only requires basic knowledge of how strings work, and the rest is implementation. We can start following the rules and you’ll be amazed at how simple the answer is.
We can only decide the amount of spaces once we have decided what words to put in a row.
part 1: find the right number of words
- find what all words we can pack in a row. assume minimal space of 1 for now.
- generate an intermediate list of all such rows, containing the correct amount of words
part 2: find the right number of spaces
- find the number of spaces required
(maxWidth - sum(len(word) for word in row))
- distribute the spacers in (almost) equal amounts to the
- last line just gets one space between words, and remaining length of maxWidth is spaces.
2. Text Justification: Implementation
class Solution: def fullJustify(self, words: List[str], maxWidth: int) -> List[str]: # get the words, ensuing min rows consumed (greedily) rows = [""] for word in words: # if emplty row, add item by default if not rows[-1]: rows[-1] += word # if can add one more word, do so elif len(rows[-1]) + 1 + len(word) <= maxWidth: rows[-1] += " " + word # else, create a new row else: rows.append(word) # get a list of words instead (spaces dont matter right now) word_rows = [row.split() for row in rows] spaced_rows =  # fix the spaces for row in word_rows[:-1]: spaces = maxWidth - sum(len(word) for word in row) # if only one word, life is easy if len(row) == 1: spaced_rows.append(row + " "*spaces) # for multiple words, else: # get the divisor and remainder # think why we use len(row)-1 :0 d, r = divmod(spaces, len(row)-1) temp = "" for word in row: # if some extra spaced remaining, consume them if r: temp += word + " "*(d + 1) r -= 1 else: temp += word + " "*d # remove the last couple of spaces spaced_rows.append(temp.strip()) # the last row has single spaced words spaced_rows.append(" ".join(word_rows[-1])) # dummy number of spaces to fill up till maxWidth spaced_rows[-1] += " "*(maxWidth - len(spaced_rows[-1])) return spaced_rows
2.1. Complexity Analysis
- Time: O(len(words) * maxWidth + len(rows) * maxWidth) for the part 1 and part 2 respectively
- Space: O(len(rows) + len(word_rows) + len(spaced_rows)) = O(len(rows)).
June 13, 2022
June 13, 2022