LeetCode Solutions Blog

Word Break II

Number: 140

Difficulty: Hard

Paid? No

Problem Description

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Words in the dictionary may be reused multiple times.

Key Insights

Use backtracking (DFS) to try splitting the string at every possible index.
Utilize memoization to store the list of valid sentences starting from a given index to avoid redundant computations.
The problem is naturally solved through recursion with memoization (a top-down dynamic programming approach).

Space and Time Complexity

Time Complexity: O(n^2 * m) in the worst case, where n is the length of the string and m is the average number of words found per recursion; memoization helps to reduce repeated work. Space Complexity: O(n * m) for the recursion stack and memoization storage, where m represents the average length of the sentence list from each index.

Solution

We use a depth-first search (DFS) that tries every possible break point in the string. At each index, if the current substring is in the dictionary, we recursively solve for the remainder of the string. Memoization is used to cache results for each index to avoid redundant computations. The solution builds the final sentences by concatenating the current word with the sentence fragments returned by the recursive call.

Code Solutions

# Python solution using memoized recursion (DFS)

def wordBreak(s, wordDict):
    word_set = set(wordDict)   # Use a set for O(1) lookups
    memo = {}  # dictionary to memoize results from each start index

    def dfs(start):
        # if reached the end of the string, return a list with empty string
        if start == len(s):
            return [""]

        if start in memo:
            return memo[start]

        sentences = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                # recursive call to get sentences for the remaining substring
                sub_sentences = dfs(end)
                # build sentences with proper spacing
                for sub in sub_sentences:
                    sentence = word + (" " + sub if sub else "")
                    sentences.append(sentence)
        
        memo[start] = sentences  # cache result
        return sentences

    return dfs(0)

# Example usage:
if __name__ == "__main__":
    s = "catsanddog"
    wordDict = ["cat", "cats", "and", "sand", "dog"]
    result = wordBreak(s, wordDict)
    print(result)  # Expected: ["cats and dog", "cat sand dog"]