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

Difficulty: interview

Starter code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        

Solutions:
class Solution:
     def wordBreak(self, s, wordDict):
         n = len(s)
         dp = [False for i in range(n+1)]
         dp[0] = True
         for i in range(1,n+1):
             for w in wordDict:
                 if dp[i-len(w)] and s[i-len(w):i]==w:
                     dp[i]=True
         return dp[-1]


class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         if not s:
             return False
         dp = [False]*(len(s)+1)
         dp[0] = True
         for i in range(len(s)+1):
             for j in range(i,-1,-1):
                 if dp[j]:
                     word = s[j:i]
                     if(word in wordDict):
                         dp[i] = True
                         break
         return dp[len(s)]

class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         word_set = set(wordDict)
         return self._dfs(s, 0, word_set, {})
     
     def _dfs(self, s, start, word_set, memoization):
         if start == len(s):
             return True
         
         if start in memoization:
             return memoization[start]
         
         for end in range(start, len(s) + 1):
             if s[start:end] in word_set and self._dfs(s, end, word_set, memoization):
                 memoization[start] = True
                 return True
         
         memoization[start] = False
         return False

class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         s_len = len(s)
         if s_len == 0:
             return True
         
         found = [True]
         for ind in range(s_len):
             if_found = False
             for i in range(ind+1):
                 # print(len(found)-i-1)
                 # print(s[(len(found)-i-1):(ind+1)])
                 if found[len(found)-i-1] and s[(len(found)-i-1):(ind+1)] in wordDict:
                     found += [True]
                     break
             if len(found) == ind + 1:
                 found += [False]
         print(found)
         return found[-1]


class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         ok = [True]
         for i in range(1, len(s)+1):
             ok += (any(ok[j] and s[j:i] in wordDict for j in range(i))),
             print(ok)
         return ok[-1]

class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         res = [True]
         for i in range(1,len(s)+1):
             res += any(res[j] and s[j:i] in wordDict for j in range(i)),
         return(res[-1])

class Solution:
     def wordBreak(self, s, wordDict):
         f = [False for _ in range(len(s))]
         for i in range(len(s)):
             if(s[:i+1] in wordDict):
                 f[i] = True
                 continue
             for j in range(i):
                 if(f[j] and s[j+1:i+1] in wordDict):
                     f[i] = True
                     break
         return f[len(s)-1]


class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         l = set(wordDict)
         stack = [-1]
         for i in range(len(s)):
             ptr = len(stack) - 1
             while ptr >= 0:
                 if s[stack[ptr] + 1:i + 1] in l:
                     stack.append(i)
                     break
                 ptr -= 1
         return stack[-1] == len(s) - 1

class Solution:
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         words = {w for w in wordDict}
         n = len(s) + 1
         ok = [False] * n
         ok[0] = True
         for j in range(1, n):
             for i in range(j):
                 if ok[i] and s[i: j] in words:
                     ok[j] = True
                     break
         return ok[-1]


class Solution:
     
     def wordBreak(self,s, words):
         d = [False] * len(s)    
         for i in range(len(s)):
             for w in words:
                 if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):
                     d[i] = True
         return d[-1]
     def wordBreak3(self, s, words):
         ok = [True]
         for i in range(1, len(s)+1):
             ok += any(ok[j] and s[j:i] in words for j in range(i)),
         return ok[-1]    
 
     def wordBreak2(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         dic={}
         def dp(s,wordDict,i):
             flag=False
             for j in range(i,len(s)+1):
                 if (i,j) not in dic:
                     if s[i:j] in wordDict:
                         if j==len(s):
                             return True
                         dic[i,j]=dp(s,wordDict,j)
                 if (i,j) in dic and dic[i,j]:
                     flag=True
                     break
             return flag        
         return dp(s,wordDict,0)

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
         """
         dp = [True] + len(s) * [False]
         for i in range(1,len(s)+1):
             for j in range(i):
                 if dp[j] == True and s[j:i] in wordDict:
                     dp[i] = True
                     break
         return dp[len(s)]
                 
         


class Solution:
     def wordBreak(self, s, words):
         ok = [True]
         for i in range(1, len(s)+1):
             ok += any(ok[j] and s[j:i] in words for j in range(i)),
         return ok[-1]

class Solution:   
     def wordBreak(self, s, wordDict):
         """
         :type s: str
         :type wordDict: List[str]
         :rtype: bool
         """
         canSplitUntilIndex = [False for x in range(len(s)+1)]
         canSplitUntilIndex[0] = True
         endIndex = 1
         while endIndex <= len(s):
             startIndex = 0
             splitIndex = startIndex
             while splitIndex < endIndex:
                 if canSplitUntilIndex[splitIndex] and s[splitIndex:endIndex] in wordDict:
                     canSplitUntilIndex[endIndex] = True
                     break
                 splitIndex += 1
             endIndex += 1
         
         return canSplitUntilIndex[len(s)]
             


class Solution:
     def wordBreak(self, s, words):
         ok = [True]
         for i in range(1, len(s)+1):
             ok += any(ok[j] and s[j:i] in words for j in range(i)),
         return ok[-1]