```
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
def dfs(i):
if i in dic:
return dic[i]
dic[i]=False
for j in xrange(i+1,min(len(s)+1,i+lens+1)):
if s[i:j] in wordSet and dfs(j):
dic[i]=True
break
return dic[i]
if not s or not wordDict:
return False
wordSet=set(wordDict)
lens=max(len(x) for x in wordSet)
dic={len(s):True}
return dfs(0)
```