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
class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         w = [0 for _ in range(len(s)+1)]
         
         for i in range(1,len(s)+1):
             if w[i] == 0 and s[:i] in wordDict:
                 w[i] = 1
             if w[i]:
                 if i == len(s):
                     return True
                 for j in range(i+1,len(s)+1):
                     if w[j] == 0 and s[i:j] in wordDict:
                         w[j] = 1
                     if j == len(s) and w[j] == 1:
                         return True
         
         return False
class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         w = [0 for _ in range(len(s)+1)]
         
         for i in range(1,len(s)+1):
             if w[i] == 0 and s[:i] in wordDict:
                 w[i] = 1
             if w[i]:
                 if i == len(s):
                     return True
                 for j in range(i+1,len(s)+1):
                     if w[j] == 0 and s[i:j] in wordDict:
                         w[j] = 1
                     if j == len(s) and w[j] == 1:
                         return True
         
         return False