算法（九）记忆化搜索

2019-06-09

本文简单介绍一下记忆化搜索（即有状态DFS），并举例分析。

1. 简介

记忆化搜索，实际上就是有状态的DFS，即在DFS过程中缓存中间变量，从而在后续计算的时候避免重复计算。

2. 举例分析

题目： 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明： 分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]

输出:
[
  "cats and dog",
  "cat sand dog"
]

代码如下

#带返回结果的dfs
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordSet = set(wordDict)
        
        @lru_cache(None)
        def dfs(index):
            if index >= len(s):
                return [[]]
            res = []
            for i in range(index+1, len(s)+1):
                word = s[index:i]
                if word in wordSet:
                    tmp = dfs(i)
                    for x in tmp:
                        res.append(x.copy()+[word])
            return res
        
        res = dfs(0)
        return [ " ".join(x[::-1]) for x in res]