python 使用递归的最大单词拆分

rbl8hiat  于 2022-12-02  发布在  Python
关注(0)|答案(1)|浏览(108)

给定一个字符串s和一个有效单词的字典d,确定使用递归可以将字符串拆分为的有效单词的最大数量
我试着用下面的代码来解决这个问题,但是它没有给我我想要的答案。有人能帮我理解递归是如何用来解决这个问题的吗?我特别想得到最大的单词数。例如-“warmontheat”可以分成最多4个单词- warm on the at。

def wordBreak( s, wordDict):
    
        if len(s)==0:
            return 0
        for end in range( 1, len(s) + 1):
            if s[0:end] in wordDict and wordBreak(s, wordDict):
                return 1
       
 
        return wordBreak(s, wordDict)

s="warmontheat"
words=("war","month","on","the","heat","eat","he","arm","at","warm")
print(wordBreak(s,words))
j2cgzkjk

j2cgzkjk1#

存在以下问题:

  • 递归调用是使用两个参数的相同值进行的,这意味着递归(如果开始)永远不会结束:条件总是相同的。递归的目的是解决一个更小的问题,所以你应该传递一个更短的字符串--没有刚刚匹配的前缀。所以传递s[end:]
  • 递归调用就像返回一个布尔值一样,但是你会想知道做了 * 多少 * 个分区,所以在if条件下进行调用是没有帮助的。你需要在if块内进行调用,并对从中得到的结果做一些事情。
  • 对于return 1,你实际上是说递归调用只把字符串分割成了 * 一个 * 分区,但这不是真的。换句话说:你的函数只能返回0或1,不能返回其他值。2相反,返回值应该取决于你从递归中得到的数字。
  • 在循环中使用return * 是错误的。可能会有这样的情况,你已经成功地使用了一个单词,但实际上需要一个替代方案,* 较长 * 的单词优先,以便从字符串的其余部分中的较短单词中获益,因此你不能假设第一个成功对应于最优解。循环必须继续进行迭代,只有当循环完成时,您可以知道哪个有效选项是最佳选项。

下面是更正后的代码:

def wordBreak(s, wordDict):
    if len(s) == 0:
        return 0
    result = float('-inf')
    for end in range(1, len(s) + 1):
        if s[:end] in wordDict:
            result = max(result, wordBreak(s[end:], wordDict))
    return 1 + result

相关问题