Given a non-empty string s and a dictionary wordDict containing a list of non-emptywords, 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.

Example 1:

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

Example 2:

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

Example 3:

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

Related Topics:Dynamic Programming

## 解題邏輯與實作

### 遞迴

1. 查詢此單字是否存在於字典中
1. 有，則回傳 True
2. 否，則向下執行
2. 使用一個指標由前向後遍歷此單字，並依指標位置，將單字拆成前後部份並呼叫遞迴傳入，唯有當前後部份皆可在字典中查到時才回傳 True，否則繼續向後遍歷。
3. 若遍歷完整個字串皆無法找到拆解法則回傳 False
 123456789101112131415161718192021222324252627282930 class Solution: def __init__(self, mydict=None): self.mydict = mydict self.memo = {} def set_dict(self,mydict): self.mydict = mydict def wordBreak(self, s, wordDict): self.set_dict(set(wordDict)) return self.check(s) def check(self, s): length = len(s) if s in self.memo: return self.memo.get(s) if length <= 0 or s in self.mydict: self.memo[s] = True return True result = False for i in range(1, length): result = self.check(s[:i]) and self.check(s[i:]) if result : break self.memo[s] = result return result 

### Dynamic Programming

 12345678910111213 class Solution: def wordBreak(self, s, wordDict): n = len(s) dp = [False] * (n + 1) dp[0] = True words = set(wordDict) for j in range(n): for i in range(j, -1, -1): if dp[i] and s[i:j + 1] in words: dp[j + 1] = True break return dp[n] 

### Dynamic Programming 改進版

 12345678910111213141516 class Solution: def wordBreak(self, s, wordDict): words = set(wordDict) maxLen = 0 for word in wordDict: maxLen = max(maxLen, len(word)) n = len(s) dp = [False] * (n + 1) dp[n] = True for i in range(n - 1, -1, -1): for j in range(i + 1, min(i + maxLen, n) + 1): if dp[j] and s[i:j] in words: dp[i] = True break return dp[0]