How do you solve Word Break II on LeetCode?

Word Break II (LeetCode #140) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Understanding the difference between recursion and memoization is crucial.

What is the brute force solution for Word Break II?

The brute force approach for Word Break II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries to generate all possible combinations of words from the string. It checks each substring to see if it exists in the dictionary and recursively builds sentences. The optimal Optimal Solution approach improves this to O(n²).

What are the interview tips for Word Break II?

Explain your thought process clearly and ask clarifying questions. Discuss time and space complexity as you develop your solution. Practice writing clean and efficient code, as readability is important.

What are common mistakes when solving Word Break II?

Not using memoization when needed, leading to excessive recursive calls. Failing to check for base cases in recursion.

#140

Word Break II

Hard

ArrayHash TableStringDynamic ProgrammingBacktrackingTrieMemoizationHash MapDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal approach uses memoization to store results of previously computed states, avoiding redundant calculations. This significantly speeds up the process by not recalculating sentences for the same starting index.

⚙️

Algorithm

3 steps

1Step 1: Create a memoization dictionary to store results for each starting index.
2Step 2: For each starting index, check all possible substrings and if they are in the dictionary.
3Step 3: Use the memoization dictionary to store and retrieve results for previously computed indices.

solution.py15 lines

1def wordBreak(s, wordDict):
2    wordSet = set(wordDict)
3    memo = {}
4    def backtrack(start):
5        if start in memo: return memo[start]
6        if start == len(s): return ['']
7        sentences = []
8        for end in range(start + 1, len(s) + 1):
9            word = s[start:end]
10            if word in wordSet:
11                for sub_sentence in backtrack(end):
12                    sentences.append(word + (" " + sub_sentence if sub_sentence else ""))
13        memo[start] = sentences
14        return sentences
15    return backtrack(0)

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops, but memoization reduces the number of recursive calls, leading to better performance in practice. Space complexity is O(n) for the memoization storage.

1Understanding the difference between recursion and memoization is crucial.
2Recognizing overlapping subproblems helps optimize solutions.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.