时间戳

首页 > 解决方案 > 递归程序打印但没有返回正确的值

python - 递归程序打印但没有返回正确的值

问题描述

我正在尝试解决一个名为 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)

标签： pythonalgorithmrecursion

解决方案

像这样的递归问题很常见，如果不让递归完成工作，您会使其变得比必要的更难。尽管@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因为要求是关于拟合是否可能的布尔结果：

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
>

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

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

推荐阅读