[Leetcode]139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Input: s = "leetcode", wordDict = ["leet", "code"] Output: true

When I saw this question I recognized it as a search problem. Treating each word in the wordDict as a node, the question is asking whether or not could we found a root-to-leaf path such that the nodes along the path compose the input string s. Therefore algorithms like DFS could work. On top of that, if you know Depth-First-Search(DFS) vs Dynamic Programming(DP), we can actually improve the time efficiency by applying dynamic programming.

DP1. Top-down with memo

We use i to indicate the current position. If we find some words in wordDict such that s[i:i+len(word)] matches, then we can move forward to check s[i+len(word):]. We can use recursion to implement this process and the exit condition would be when we finishing scanning the whole input string s.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @lru_cache(None)
        def helper(index=0):
            if index == len(s):
                return True
            return any(helper(index+len(word)) for word in wordDict\
               if index+len(word)<=len(s) and s[index:index+len(word)] == word)
        return helper()

DP2. Bottom-up

Or simply we could implement a dp array where dp[i] indicates whether s[:i+1] could be successfully segmented. With bottom-up approach, we would look back when determine dp[i] – to check if s[i:j] is in wordDict and dp[i] is True.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [1] # dp[i] means s[:i] could be segmented as required
        for i in range(1,len(s)+1):
            dp += [any(dp[j] and s[j:i] in wordDict for j in range(i))]
        return dp[-1]

Or if we look forward during the loop – when processing dp[i], we set the value for dp[i+len(word)] if s[i:i+len(word)] is in wordDict.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [0] * (len(s)+1)
        dp[0] = 1
        for i in range(len(s)+1):
            if dp[i]:
                for word in wordDict:
                    if s[i:i+len(word)]==word:
                        dp[i+len(word)] = 1
        return dp[-1]