leetcode：139. 单词拆分【dfs + memory】

分析

一个个选，如果是前缀就可以选
如果在里面就返回True
记忆化参数，某个s
结果：能否由这个dict组成，返回bool

先特判in
然后一个个dict里面的word看，如果是前缀
就dfs去掉前缀的，如果为真，就返回True
如果全部都不返回True，返回False

这个就是把能找的都找了，实在返回不了True也就没有办法了哦

ac code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @cache
        def dfs(s):
            if s in wordDict:
                return True
            
            for word in wordDict:
                if s.startswith(word):
                    if dfs(s[len(word):]):
                        return True

            return False
        
        return dfs(s)

总结

dfs记忆化搜索优雅如斯