Untitled

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        MAX_WORD_LENGTH = max(len(word) for word in wordDict)

        @cache
        def dp(i=0):
            if i==len(s):
                return True
            for j in range(min(i+MAX_WORD_LENGTH, len(s))):
                if s[i:j+1] in words and dp(j+1):
                    return True
            return False

        return dp()