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

        #TC: O(n^2)
        #SC: O(n)

        if len(s) == 0 or len(wordDict) == 0:
            return False

        Memory = {}
        Set = set(wordDict)

        def dfs(s):

            if s in Memory:
                return Memory[s]

            if s in Set:
                Memory[s] = True
                return True

            for i in range(1, len(s)):
                l = s[:i]
                r = s[i:]

                if l in Set:
                    Memory[l] = True
                    if dfs(r):
                        Memory[s] = True
                        return True
            Memory[s] = False
            return False

        return dfs(s)