class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo={}
        return self.wordBreak1(s, wordDict, memo)
    
    def wordBreak1(self, s: str, wordDict: List[str], memo={}) -> bool:
        if s == "":
            return True
        if s in memo:
            return memo[s]
        for word in wordDict:
            l = len(word)
            sp = s[:l]
            if sp == word:
                memo[s] = self.wordBreak1(s[l:], wordDict)
                if memo[s] == True:
                    return True 
            
        memo[s] = False
        return False

"applepie"
["pie","pear","apple","peach"]