python - python中带记忆的动态编程

Question

我正在尝试编写一个代码来检查一个单词是否可以“分解”成某个列表中的单词组合。例如，如果我的输入是：

word = 'strawberryfield'
list = ['straw', 'berry', 'field']

然后程序应该返回True。

我设法编写的代码是：

class Solution(object):
    def wordBreakInner(self, s, wordDict, memo):
        # print("entered with: ", s)
        
        if s in memo:
            return memo[s]
        
        if len(s) == 0 or s in wordDict:
            memo.append(s)
            return True
        
        for i in range(len(s)):
            if s[0:i:1] in wordDict:
                # print("found this word in dict: ", s[0:i:1])
                if s[i:] in memo:
                    return true
                else:
                    if self.wordBreakInner(s[i:], wordDict, memo):
                        memo.append(s)
                        return True
        return False
        
        
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        return self.wordBreakInner(s, wordDict, [])

它似乎有效，但无法处理长输入。这就是为什么我尝试添加记忆处理（不确定我是否做得很好）。对于以下输入，程序时间限制超过：

word = 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab'
['a', 'aa', 'aaa', 'aaaa', 'aaaaa', 'aaaaaa', 'aaaaaaa', 'aaaaaaaa', 'aaaaaaaaa', 'aaaaaaaaaa']

有人可以解释我做错了什么吗？我很确定它与记忆有关，但我不知道为什么。

标签： pythondynamic-programming