[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.
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.

Top down approach.
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        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]
Notify of
Inline Feedbacks
View all comments