LeetCode 140: Word Break II Solution in Python Explained

Problem Statement

In LeetCode 140, you’re given a string s and a list of strings wordDict. Your task is to return a list of all possible space-separated sequences of dictionary words that concatenate to form s (words can be reused). This builds on LeetCode 139: Word Break, which checks existence, to listing all segmentations, differing from list copying like LeetCode 138: Copy List with Random Pointer.

Constraints

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of lowercase English letters
• All words in wordDict are unique

Example

Let’s see some cases:

Copy codeInput: s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
Output: ["cats and dog", "cat sand dog"]
Explanation: 
<ul>
<li>"cats" + "and" + "dog" = "catsanddog"</li>
<li>"cat" + "sand" + "dog" = "catsanddog"</li>
</ul>

Copy codeInput: s = "pineapplepenapple", wordDict = ["apple", "pen", "pine", "pineapple"]
Output: ["pine apple pen apple", "pineapple pen apple", "pine apple pen apple"]
Explanation: 
<ul>
<li>"pine" + "apple" + "pen" + "apple"</li>
<li>"pineapple" + "pen" + "apple"</li>
<li>Duplicate due to overlap, but all valid.</li>
</ul>

Copy codeInput: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: []
Explanation: No valid segmentation.

These examples show we’re collecting all possible segmentations.

Understanding the Problem

How do you solve LeetCode 140: Word Break II in Python? Take s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]. We need all ways to break it: "cats and dog" and "cat sand dog", so return ["cats and dog", "cat sand dog"]. For "catsandog", no full segmentation works, so []. This isn’t a singleton search like LeetCode 137: Single Number II; it’s about enumerating all string decompositions. We’ll use: 1. Dynamic Programming with Backtracking: O(n * 2^n) time, O(n) space—our best solution (n = string length). 2. Recursive with Memoization: O(n * 2^n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dynamic Programming with Backtracking Approach

Explanation

Dynamic Programming with Backtracking uses a DP array dp where dp[i] stores all possible segmentations of s[i:]. It builds bottom-up, starting from the end, and for each position i, tries all dictionary words ending at i, combining them with segmentations of the remaining string. This is the best solution due to its efficiency in avoiding redundant string construction, clear bottom-up approach, and manageable space usage, making it both practical and optimized for this problem.

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

• dp[10] = [""] (empty).
• dp[7] = ["dog"] ("dog" ends at 10).
• dp[3] = ["sand dog", "and dog"].
• dp[0] = ["cats and dog", "cat sand dog"].

Step-by-Step Example

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

Goal: Return ["cats and dog", "cat sand dog"].

• Start: dp = [[] for _ in range(11)], n = 10.
• Step 1: i=10, dp[10] = [""] (empty string).
• Step 2: i=7, "dog" matches, dp[7] = ["dog"].
• Step 3: i=6, "and" from 3, dp[6] = ["and dog"].
• Step 4: i=4, "sand" from 0, dp[4] = ["sand dog"].
• Step 5: i=3, "cat" from 0, dp[3] = ["cat sand dog"].
• Step 6: i=0, "cats" from 0, "cat" + dp[3], dp[0] = ["cats and dog", "cat sand dog"].
• Finish: Return dp[0].

Example 2: s = "pineapplepenapple", wordDict = ["apple", "pen", "pine", "pineapple"]

Goal: Return ["pine apple pen apple", "pineapple pen apple"].

• Start: dp = [[] for _ in range(18)], n = 17.
• Step 1: i=17, dp[17] = [""].
• Step 2: i=12, "apple", dp[12] = ["apple"].
• Step 3: i=9, "pen", dp[9] = ["pen apple"].
• Step 4: i=4, "apple", dp[4] = ["apple pen apple"].
• Step 5: i=0:
• "pine" + dp[4], dp[0] += ["pine apple pen apple"].
• "pineapple" + dp[9], dp[0] += ["pineapple pen apple"].
• Finish: Return ["pine apple pen apple", "pineapple pen apple"].

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

Goal: Return [].

• Start: dp = [[] for _ in range(10)], n = 9.
• Step 1: i=9, no match, dp[9] = [].
• Step 2: i=7, "and" needs "og", dp[7] = [].
• Step 3: Continue, dp[0] = [] (no full segmentation).
• Finish: Return [].

How the Code Works (Dynamic Programming with Backtracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef wordBreak(s: str, wordDict: list[str]) -> list[str]:
    # Line 1: Get string length and word set
    n = len(s)
    # Length of input string (e.g., 10 for "catsanddog")
    word_set = set(wordDict)
    # O(1) lookup (e.g., {"cat", "cats", "and", "sand", "dog"})

    # Line 2: Initialize DP array
    dp = [[] for _ in range(n + 1)]
    # dp[i] = list of segmentations for s[i:] (e.g., [[]]*11)
    dp[n] = [""]
    # Base case: empty string is one empty segmentation

    # Line 3: Build DP from right to left
    for i in range(n - 1, -1, -1):
        # i = start index (e.g., 9 to 0)

        # Line 4: Try each possible word ending at i+k
        for k in range(i + 1, n + 1):
            # k = end index (e.g., i+1 to n)
            word = s[i:k]
            # Substring to check (e.g., "dog" for i=7, k=10)

            # Line 5: If word is in dictionary
            if word in word_set:
                # e.g., "dog" in set
                for sub in dp[k]:
                    # sub = segmentation of s[k:] (e.g., "" for k=10)
                    if sub:
                        # If sub is non-empty, add space
                        dp[i].append(word + " " + sub)
                    else:
                        # If sub is empty (end), no space
                        dp[i].append(word)
                # e.g., dp[7] = ["dog"], dp[6] = ["and dog"]

    # Line 6: Return all segmentations from start
    return dp[0]
    # Final list (e.g., ["cats and dog", "cat sand dog"])

This detailed breakdown clarifies how DP with backtracking efficiently builds all segmentations.

Alternative: Recursive with Memoization Approach

Explanation

Recursive with Memoization uses a top-down approach, caching segmentations for each starting index in a memoization dictionary, recursively trying all dictionary words and combining results. It’s a practical alternative, also exponential but optimized to O(n * 2^n) with memoization, using O(n) space for the cache, though less intuitive than bottom-up DP.

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

• From 0: "cats" + "anddog", "cat" + "sanddog".
• Memoized subproblems yield all paths.

Step-by-Step Example (Alternative)

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

• Start: dfs(0).
• Step 1: "cats" + dfs(4) → "and" + dfs(7) → "dog" + dfs(10) → "cats and dog".
• Step 2: "cat" + dfs(3) → "sand" + dfs(7) → "dog" + dfs(10) → "cat sand dog".
• Finish: ["cats and dog", "cat sand dog"].

How the Code Works (Recursive with Memoization)

Copy codedef wordBreakRecursive(s: str, wordDict: list[str]) -> list[str]:
    word_set = set(wordDict)
    memo = {}

    def dfs(start: int) -> list[str]:
        if start == len(s):
            return [""]
        if start in memo:
            return memo[start]
        result = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                sub_words = dfs(end)
                for sub in sub_words:
                    result.append(word + (" " + sub if sub else ""))
        memo[start] = result
        return result

    return dfs(0)

Complexity

• Dynamic Programming with Backtracking:
• Time: O(n * 2^n) – exponential due to all segmentations.
• Space: O(n) – DP array and string storage.
• Recursive with Memoization:
• Time: O(n * 2^n) – memoized exponential calls.
• Space: O(n) – memoization cache.

Efficiency Notes

Dynamic Programming with Backtracking is the best solution with O(n * 2^n) time and O(n) space, offering clarity and efficiency—Recursive with Memoization matches complexity but uses recursion overhead, making it a flexible alternative, though less straightforward.

Key Insights

• DP: Builds segmentations bottom-up.
• Memoization: Caches top-down results.
• All Paths: Enumerates every possibility.

Additional Example

For s = "catdog", wordDict = ["cat", "dog"]:

• Goal: ["cat dog"].
• DP: dp[6] = ["dog"], dp[0] = ["cat dog"].

Edge Cases

• Empty String: "", ["a"] → [""].
• Single Word: "a", ["a"] → ["a"].
• No Match: "a", ["b"] → [].

Both solutions handle these well.

Final Thoughts

LeetCode 140: Word Break II in Python is a challenging string segmentation puzzle. The Dynamic Programming with Backtracking solution excels with its efficiency and structure, while Recursive with Memoization offers a top-down approach. Want more? Try LeetCode 139: Word Break for the simpler version or LeetCode 94: Binary Tree Inorder Traversal for tree basics. Ready to practice? Solve LeetCode 140 on LeetCode with "catsanddog" and ["cat", "cats", "and", "sand", "dog"], aiming for ["cats and dog", "cat sand dog"]—test your skills now!