Word Break II

TypeDynamic Programming
Difficulty
Hard
Last Reviewed12/28/2024

Problem Description

Given a string and a dictionary of words, add spaces in the string to construct sentences where each word is a valid word according to the dictionary. Return all possible sentences.

Example 1

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

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

Explanation: Input: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"] Output: ["cat sand dog","cats and dog"] Explanation: The input string can be segmented into "cat sand dog" and "cats and dog" using words from the wordDict.

Example 2

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

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

Explanation: Input: s = "pineapplepenapple", wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: ["pine apple pen apple","pineapple pen apple"] Explanation: The input string can be segmented into "pine apple pen apple" and "pineapple pen apple" using words from the wordDict.

Example 3

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

Output: []

Explanation: Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: [] Explanation: The input string cannot be segmented into words from the wordDict.

Solution Overview

Initial Approach

I will use dynamic programming to break down the problem into smaller subproblems and memoize the results to avoid recomputation. Then, I will backtrack to generate all possible valid sentences.

Step by Step Solution

  1. 1. Create a set to store all words for quick lookup.
  2. 2. Initialize a memoization dictionary to store the results of subproblems.
  3. 3. Define a recursive function that takes a starting index and returns all valid sentences starting from that index.
  4. 4. Inside the recursive function, check if the substring from the starting index is in the memoization dictionary. If so, return the cached results.
  5. 5. Iterate over the substring starting from the starting index and check if a prefix of the substring is in the word set.
  6. 6. If a valid prefix is found, recursively call the function with the next index and append the prefix to the sentences generated from the recursive call.
  7. 7. Memoize the results for the current index and return all valid sentences.

Solution Code

1class Solution:
2    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
3        def backtrack(start, path):
4            if start == len(s):
5                result.append(' '.join(path))
6                return
7            for end in range(start + 1, len(s)+1):
8                if s[start:end] in wordDict:
9                    backtrack(end, path + [s[start:end]])
10        result = []
11        backtrack(0, [])
12        return result

Solution Walkthrough

"catsanddog", ["cat", "cats", "and", "sand", "dog"]

Step 1

1backtrack(0, [])

Start the backtracking process with start index 0 and an empty path

State: Current string: catsanddog Current path: [] Result: []

Step 2

1if start == len(s):

Check if we have reached the end of the string

State: Current string: catsanddog Current path: [] Result: []

Step 3

1for end in range(start + 1, len(s)+1):

Iterate over all possible end indices starting from the current start index

State: Current string: catsanddog Current path: [] Result: []

Step 4

1if s[start:end] in wordDict:

Check if the substring from start to end is in the word dictionary

State: Current string: catsanddog Current path: [] Result: []

Step 5

1backtrack(end, path + [s[start:end]])

Recursively call backtrack with the new start index and updated path

State: Current string: catsanddog Current path: ["cat"] Result: []

Step 6

1result.append(' '.join(path))

Add the current valid path to the result list

State: Current string: catsanddog Current path: ["cat"] Result: ["cat"]

Complexity Analysis

Time Complexity: exponential

The time complexity of the solution is exponential because of the recursive nature of the algorithm. The number of recursive calls grows exponentially with the length of the input string.

Space Complexity: O(n * 2^n)

In the worst case, we can have 2^n possible substrings for each of the n characters in the input string.

Breakdown:

    Algorithmic Patterns

    Backtracking

    How it's used: Generate and explore all possible solutions by making choices and undoing them if they lead to a dead-end

    Where in code: Within the recursive function that explores all possible solutions

    Example: Generating all possible combinations in a list of integers

    Common Mistakes

    Mistake 1

    What: Not handling empty input or edge cases

    Why: This can lead to runtime errors or incorrect outputs

    How to avoid: Always check and handle empty input or edge cases

    Mistake 2

    What: Not considering all possible word combinations

    Why: This can result in missing valid solutions

    How to avoid: Ensure to explore all possible word combinations recursively

    Mistake 3

    What: Not optimizing for efficiency

    Why: Inefficient algorithms can lead to timeouts for large inputs

    How to avoid: Use dynamic programming or memoization to optimize performance

    Interview Tips

    • Understand the problem constraints and requirements clearly
    • Break down the problem into smaller subproblems
    • Consider using dynamic programming for efficiency