class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        res = [False]
        mapp = dict()
        self.recursive(s, set(wordDict), 0, res, mapp)
        return res[0]




    def recursive(self, s, words, i, res, mapp):
        if i >= len(s):
            return False

        if i in mapp:
            return mapp[i]

        if s[i: len(s)] in words:
            res[0] = True
            return True

        j = i
        while j < len(s):
            if s[i:j+1] in words:
                result = self.recursive(s, words, j+1, res, mapp)
                mapp[j+1] = result
                if result:
                    return result
            j += 1