LeetCode 139: Word Break Solution in Python Explained

Problem Statement

In LeetCode 139, you’re given a string s and a list of strings wordDict. Your task is to return true if s can be segmented into a space-separated sequence of words from wordDict (words can be reused), or false if no such segmentation exists. This differs from linked list copying like LeetCode 138: Copy List with Random Pointer, focusing on string segmentation rather than list duplication.

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 = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" = "leet" + "code".

Copy codeInput: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: "applepenapple" = "apple" + "pen" + "apple".

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

These examples show we’re checking if the string can be fully segmented.

Understanding the Problem

How do you solve LeetCode 139: Word Break in Python? Take s = "leetcode", wordDict = ["leet", "code"]. We need to see if "leetcode" can be broken into "leet" + "code"—it can, so return true. For "catsandog", no combination from ["cats", "dog", "sand", "and", "cat"] works (e.g., "cats" + "and" leaves "og"), so false. This isn’t a singleton search like LeetCode 137: Single Number II; it’s about string decomposition. We’ll use: 1. Dynamic Programming Bottom-Up: O(n * m * k) time, O(n) space—our best solution (n = string length, m = wordDict length, k = average word length). 2. Recursive with Memoization: O(n * m * k) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dynamic Programming Bottom-Up Approach

Explanation

Dynamic Programming Bottom-Up uses a boolean array dp where dp[i] is true if the substring s[0:i] can be segmented into dictionary words. For each position i, check all possible word endings from previous dp[j] positions, marking dp[i] true if a valid word is found. This is the best solution due to its O(n * m * k) time complexity, O(n) space, and clear, efficient approach that avoids redundant recursive calls, making it both fast and intuitive.

For "leetcode", wordDict = ["leet", "code"]:

• dp[0] = true (empty string).
• dp[4] = true ("leet" from 0).
• dp[8] = true ("code" from 4).
• Result: true.

Step-by-Step Example

Example 1: s = "leetcode", wordDict = ["leet", "code"]

Goal: Return true.

• Start: dp = [true, false, false, false, false, false, false, false, false], n = 8.
• Step 1: i=1, "l", no match, dp[1] = false.
• Step 2: i=4, "leet", matches "leet" from 0, dp[4] = true.
• Step 3: i=8, "leetcode", "code" from 4, dp[8] = true.
• Finish: dp[8] = true, return true.

Example 2: s = "applepenapple", wordDict = ["apple", "pen"]

Goal: Return true.

• Start: dp = [true, false, ..., false] (length 14).
• Step 1: i=5, "apple", matches "apple" from 0, dp[5] = true.
• Step 2: i=8, "applepen", "pen" from 5, dp[8] = true.
• Step 3: i=13, "applepenapple", "apple" from 8, dp[13] = true.
• Finish: dp[13] = true, return true.

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

Goal: Return false.

• Start: dp = [true, false, ..., false] (length 10).
• Step 1: i=3, "cat", matches "cat", dp[3] = true.
• Step 2: i=4, "cats", matches "cats", dp[4] = true.
• Step 3: i=7, "catsand", "and" from 4, dp[7] = true.
• Step 4: i=9, "catsandog", no match from 7 ("og" not in dict), dp[9] = false.
• Finish: dp[9] = false, return false.

How the Code Works (Dynamic Programming Bottom-Up) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef wordBreak(s: str, wordDict: list[str]) -> bool:
    # Line 1: Get string length
    n = len(s)
    # Length of input string (e.g., 8 for "leetcode")

    # Line 2: Convert wordDict to set for O(1) lookup
    word_set = set(wordDict)
    # Faster lookups (e.g., {"leet", "code"})

    # Line 3: Initialize DP array
    dp = [False] * (n + 1)
    # dp[i] = true if s[0:i] can be segmented (e.g., [False]*9)
    dp[0] = True
    # Empty string is segmentable (base case)

    # Line 4: Iterate over all ending positions
    for i in range(1, n + 1):
        # i = end index (e.g., 1 to 8)

        # Line 5: Check all possible start positions
        for j in range(i):
            # j = start index (e.g., 0 to i-1)

            # Line 6: Check if substring s[j:i] is a word
            if dp[j] and s[j:i] in word_set:
                # If s[0:j] is segmentable and s[j:i] is in dict
                # e.g., j=0, i=4, dp[0]=true, "leet" in set
                dp[i] = True
                # Mark s[0:i] as segmentable (e.g., dp[4]=true)
                break
                # Move to next i since one segmentation suffices

    # Line 7: Return if entire string is segmentable
    return dp[n]
    # Final value (e.g., dp[8]=true for "leetcode")

This detailed breakdown clarifies how dynamic programming efficiently checks segmentation.

Alternative: Recursive with Memoization Approach

Explanation

Recursive with Memoization uses a top-down approach, recursively checking if substrings can be segmented, caching results to avoid recomputation. It tries each word from the dictionary at the start, recurring on the rest. This is a practical alternative, also O(n * m * k) time, but O(n) space for memoization, and slightly less intuitive than bottom-up DP.

For "leetcode", ["leet", "code"]:

• "leet" + check("code") → "code" matches, true.
• Cache ensures efficiency.

Step-by-Step Example (Alternative)

For "applepenapple", ["apple", "pen"]:

• Start: dfs(0).
• Step 1: "apple" from 0, dfs(5).
• "pen" from 5, dfs(8).
• "apple" from 8, dfs(13) → true (empty).
• Return true.
• Finish: Return true.

How the Code Works (Recursive with Memoization)

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

    def dfs(start: int) -> bool:
        if start == len(s):
            return True
        if start in memo:
            return memo[start]
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and dfs(end):
                memo[start] = True
                return True
        memo[start] = False
        return False

    return dfs(0)

Complexity

• Dynamic Programming Bottom-Up:
• Time: O(n * m * k) – n positions, m words, k avg word length.
• Space: O(n) – DP array.
• Recursive with Memoization:
• Time: O(n * m * k) – memoized calls.
• Space: O(n) – memoization cache.

Efficiency Notes

Dynamic Programming Bottom-Up is the best solution with O(n * m * k) 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 from substrings.
• Memoization: Caches recursive results.
• Segmentation: Word-by-word breakdown.

Additional Example

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

• Goal: true.
• DP: dp[3] = true ("cat"), dp[6] = true ("dog").

Edge Cases

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

Both solutions handle these well.

Final Thoughts

LeetCode 139: Word Break in Python is a rewarding string challenge. The Dynamic Programming Bottom-Up solution excels with its efficiency and simplicity, while Recursive with Memoization offers a top-down perspective. Want more? Try LeetCode 91: Decode Ways for string decoding or LeetCode 94: Binary Tree Inorder Traversal for tree basics. Ready to practice? Solve LeetCode 139 on LeetCode with "leetcode" and ["leet", "code"], aiming for true—test your skills now!