[LeetCode] 139. Word Break

1. Question

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

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

2. Thoughts

divide the expression into left and right.
Using recursion, calculate left and right.
Use Memoization and set conversion for optimization

3. Tips learned

4. My solution

class Solution:
    def __init__(self):
        self.memo = {}

    def breakWord(self, s, wordDict):
        if s in self.memo:
            return self.memo[s]

        for word in wordDict:
            index = s.find(word)
            if index != -1:
                if s == word:
                    return True
                left = right = True
                if index != 0:
                    left = self.breakWord(s[:index], wordDict)
                if index + len(word) != len(s):
                    right = self.breakWord(s[index + len(word) :], wordDict)
                if left and right:
                    self.memo[s] = True
                    return True
                else:
                    self.memo[s] = False

        return False

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDictSet = set(wordDict)
        return self.breakWord(s, wordDictSet)

46/46 cases passed (54 ms)
Your runtime beats 6.26 % of python3 submissions
Your memory usage beats 48.08 % of python3 submissions (16.8 MB)

5. AI Solution and Improvements

Your solution uses a recursive approach with memoization to solve the problem, which is a valid and effective method, especially for reducing the number of redundant computations. However, this solution might have unnecessary checks, especially with how it handles the left and right parts around the found word. Also, using find() and then recursively checking substrings before and after the found word might lead to some inefficiency.

A more streamlined and possibly faster approach is to use dynamic programming. The idea is to use a boolean array dp of length n + 1 (where n is the length of the input string s), where dp[i] represents whether the substring s[:i] can be segmented into one or more dictionary words. Here's how you can implement it:

1. Initialize dp[0] = True because an empty string can always be segmented (it doesn't need to be segmented).
2. Iterate through the string s from i = 1 to n, and for each i, iterate through the dictionary words. If a word matches the end of the substring ending at i and dp[j] is True (where j is the start index of this word in the substring), then set dp[i] = True.
3. dp[n] will give you the answer, where n is the length of the input string s.

Here's how you can implement this approach:

def wordBreak(s, wordDict):
    wordSet = set(wordDict)  # Convert list to set for O(1) lookup
    dp = [False] * (len(s) + 1)
    dp[0] = True  # Base case: empty string

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break  # No need to check further if we found a valid word ending at i

    return dp[len(s)]

This solution uses dynamic programming to efficiently solve the problem by building up the solution from smaller problems. It avoids the overhead of recursive calls and simplifies the handling of substrings.