#140

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Word Break II

Given a string and dictionary, return all possible sentences by adding spaces where each word is in the dictionary.

array hash table string dynamic programming backtracking

Problem Statement

Given a string s and a dictionary of words wordDict, return all possible ways to add spaces in s so that each word in the resulting sentence is present in wordDict. Words in the dictionary may be reused multiple times. You need to return all valid sentences in any order.

For example, given s = "catsanddog" and wordDict = ["cat", "cats", "and", "sand", "dog"], the function should return ["cats and dog", "cat sand dog"]. The task involves dynamic programming, backtracking, and memoization techniques, utilizing an array scanning approach plus hash lookups.

Examples

Example 1

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]

Output: ["cats and dog","cat sand dog"]

Example details omitted.

Example 2

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]

Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

Note that you are allowed to reuse a dictionary word.

Example 3

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Output: []

Example details omitted.

Constraints

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
Input is generated in a way that the length of the answer doesn't exceed 105.

Solution Approach

Dynamic Programming with Backtracking

We can approach the problem using dynamic programming (DP) with a backtracking strategy. First, we define a DP array where each entry stores a list of valid sentences up to that index. For each valid word found in the string that matches a word in the dictionary, we recursively try to break down the remaining string, building valid sentences. Memoization helps to store intermediate results to avoid redundant calculations, making the solution more efficient.

Array Scanning Plus Hash Lookup

The algorithm relies on array scanning where we check every substring of the given string. For each substring, we check if it exists in the dictionary using a hash set (for fast lookup). Once a match is found, the problem breaks down into solving for the rest of the string, which can be done recursively. This method reduces time complexity by ensuring we only compute valid sentences once and avoids recalculating overlapping subproblems.

Memoization for Optimization

Memoization stores results of previously computed subproblems. If a substring has been processed before, it retrieves the result instead of recomputing it. This significantly reduces unnecessary work, especially in overlapping subproblems, as we don't have to re-solve the same substring multiple times. Memoization ensures that each substring is computed only once, improving efficiency for larger inputs.

Complexity Analysis

Metric	Value
Time	O(n \cdot 2^n)
Space	O(n \cdot 2^n)

The time complexity of this approach is O(n * 2^n), where n is the length of the string. The space complexity is also O(n * 2^n) due to storing the possible results for substrings in the DP table. This ensures that even if we explore multiple valid combinations, we store each result efficiently.

What Interviewers Usually Probe

Do you understand how dynamic programming and backtracking work together in this problem?
Can you explain why memoization significantly improves the efficiency of this solution?
Will you be able to identify the pattern in an input string and apply the array scanning approach with hash lookup?

Common Pitfalls or Variants

Common pitfalls

Failing to handle substrings that are not valid words in the dictionary.
Overlooking memoization which may lead to recalculating the same substrings repeatedly, slowing down the solution.
Not considering the case where no valid sentence exists and returning an empty result when necessary.

Follow-up variants

Word Break I: Given the same problem without needing to return all possible sentences, just checking for a valid segmentation.
Word Break III: Given a string and dictionary, return the minimum number of spaces needed to split the string into valid words.
Word Break IV: Similar to Word Break II, but with additional constraints on the number of dictionary words allowed.

FAQ

What is the approach used in Word Break II?

The approach involves dynamic programming combined with backtracking and memoization. This allows us to build valid sentences while reducing redundant calculations by storing intermediate results.

Why is memoization important in Word Break II?

Memoization is crucial because it avoids recalculating the same substrings multiple times, significantly reducing the time complexity when there are overlapping subproblems.

How does array scanning help in solving Word Break II?

Array scanning helps by efficiently checking every possible substring in the given string. If a substring is found in the dictionary, it is recursively processed, enabling the solution to build valid sentences.

What happens when no valid sentence is found in Word Break II?

If no valid sentence is found, the function should return an empty list, indicating that it's impossible to break the string into valid words from the dictionary.

How does Word Break II relate to Word Break I?

Word Break II extends Word Break I by requiring the return of all possible valid sentences instead of just checking if a valid segmentation exists.

terminal

Solution

Solution 1

#### Python3

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return False
            node = node.children[idx]
        return node.is_end


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        def dfs(s):
            if not s:
                return [[]]
            res = []
            for i in range(1, len(s) + 1):
                if trie.search(s[:i]):
                    for v in dfs(s[i:]):
                        res.append([s[:i]] + v)
            return res

        trie = Trie()
        for w in wordDict:
            trie.insert(w)
        ans = dfs(s)
        return [' '.join(v) for v in ans]

Continue Practicing

#139 word break #691 stickers to spell word #792 number of matching subsequences