139. Word Break

link

Backtrack

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

        wordDict.sort()

        @cache
        def backtrack(ii):
            if ii == n:
                return True

            res = False

            for w in wordDict:
                if s[ii:ii+len(w)] == w:
                    if backtrack(ii+len(w)):
                        return True

            return False

        return backtrack(0)

dp

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

        dp = [0] * (len(s) + 1)

        dp[0] = 1

        wordDict.sort(key=lambda x:len(x))

        for i in range(1, len(dp)):
            for w in wordDict:
                if (i < len(w)):
                    break
                if dp[i - len(w)] == 1 and  s[i - len(w):i] == w:
                    dp[i] = 1
                    break

        return dp[-1] == 1