[数据结构与算法]139.单词拆分

• 我的回溯：超时

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

        def backtrack(s):
            if len(s) == 0: self.res = True
            if self.res: return

            for i in range(1, len(s) + 1):
                if s[:i] in self.wordDict:
                    backtrack(s[i:])


        backtrack(s)
        return self.res

样例：“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab”
[“a”,“aa”,“aaa”,“aaaa”,“aaaaa”,“aaaaaa”,“aaaaaaa”,“aaaaaaaa”,“aaaaaaaaa”,“aaaaaaaaaa”]

• 加上functools库的LRU缓存后通过

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

        import functools
        @functools.lru_cache(None)
        def backtrack(s):
            if len(s) == 0: self.res = True
            if self.res: return

            for i in range(1, len(s) + 1):
                if s[:i] in self.wordDict:
                    backtrack(s[i:])


        backtrack(s)
        return self.res

• 记忆化回溯
  

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        import functools
        @functools.lru_cache(None)
        def back_track(s):
            if(not s):
                return True
            res=False
            for i in range(1,len(s)+1):
                if(s[:i] in wordDict):
                    res=back_track(s[i:]) or res
            return res
        return back_track(s)

参考链接：动态规划+记忆化回溯 逐行解释 python3

• 动态规划
  
  

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        slen = len(s)
        dp = [False]* (slen+1)
        dp[0] = True

        for i in range(slen):
            for j in range(i+1, slen+1):
                if dp[i] and s[i:j] in wordDict:
                    dp[j] = True
            
        return dp[-1]