### problem

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.

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

### solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` ``````def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: bool """ if s in wordDict: return True for i in range(1, len(s)): if s[0:i] in wordDict: if self.wordBreak(s[i:], wordDict) == True: return True return False ``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````def wordBreak(self, s, wordDict): if not s: return True dp = [False] * (len(s) + 1) dp[0] = True for i in range(1, len(s) + 1): for j in range(i): if dp[j] and s[j:i] in wordDict: dp[i] = True break return dp[len(s)] ``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 `````` ``````def wordBreak(self, s, wordDict): if not s: return True dp = [False] * (len(s)+1) dp[0] = True for i in range(len(s)): if not dp[i]: continue for word in wordDict: end = i + len(word) if end > len(s): continue if dp[end]: continue if s[i:end] == word: dp[end] = True return dp[len(s)] ``````