class Solution(object):
def breakHelper(self, memo, s, wordDict):
if s in memo.keys():
return memo[s]
else:
if (s in wordDict):
memo[s] = True
return True
for word in wordDict:
if (len(word) > len(s)):
continue
else:
# check if this word exists in the string...
flag = True
for pos in range(0, len(word)):
if (word[pos] != s[pos]):
flag = False
break
if (flag):
if self.breakHelper(memo, s[len(word):], wordDict):
memo[s] = True
return True
else:
continue
memo[s] = False
return False
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
memo = {}
return self.breakHelper(memo, s, wordDict)
Mistake: in recursion, forget to call the helper function instead of the original function.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.