python - 递归程序打印但不返回正确值

Question

我正在尝试解决一个名为 word break https://leetcode.com/problems/word-break/ 的 leetcode 问题

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，确定 s 是否可以被分割成一个或多个字典单词的空格分隔序列。

我能够打印适合该解决方案的不同分词符，但在返回我的代码时总是返回 None。我怎样才能修复它，使 res 是一个包含字典中创建 s 的不同单词的数组

import sys; 

class Solution:
    def wordBreak(self, s, wordDict):
        res = self.driver(s, 0, len(s), wordDict, [])
        print(res)

    def driver(self, text, start, end, wordDict, res):
        if text[start:end] == None:    
            return res
        elif text[start:end] in wordDict:
            result = text[start:end]
            res.append(result)
            print(res)
            return self.driver(text, end, len(text), wordDict, res)
        else:
            for i in range(start, end):
                self.driver(text, start, i, wordDict, res)

Answer 1

像这样的递归问题很常见，如果不让递归完成工作，就会使问题变得比必要的更难。虽然@blhsing 的解决方案很优雅 (+1)，但让我们处理您的设计，但要简化它:

class Solution:
    def wordBreak(self, s, wordDict):
        return self.wordBreak_recursive(s, 0, len(s), wordDict)

    def wordBreak_recursive(self, s, start, end, wordDict):

        for index in range(start + 1, end + 1):
            if s[start:index] in wordDict and (index == end or self.wordBreak_recursive(s, index, end, wordDict)):
                return True

        return False

没有必要在 res 中收集段，因为要求是关于拟合是否可能的 bool 结果:

solver = Solution()

print(solver.wordBreak("leetcode", ["leet", "code"]))
print(solver.wordBreak("applepenapple", ["apple", "pen"]))
print(solver.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))

输出

> python3 test.py
True
True
False
> 

同样，我们不需要找到所有的解决方案，只需找到一个即可。

最后，如果您的递归方法返回一个值，那么无论何时我们递归调用它，我们通常都需要处理返回值，而不是忽略它——即使递归方法通过修改其调用者的变量来确保结果环境。否则，也许它不应该返回任何东西。