给定一个字符串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))
1条答案
按热度按时间j2cgzkjk1#
存在以下问题:
s[end:]
。if
条件下进行调用是没有帮助的。你需要在if
块内进行调用,并对从中得到的结果做一些事情。return 1
,你实际上是说递归调用只把字符串分割成了 * 一个 * 分区,但这不是真的。换句话说:你的函数只能返回0或1,不能返回其他值。2相反,返回值应该取决于你从递归中得到的数字。return
* 是错误的。可能会有这样的情况,你已经成功地使用了一个单词,但实际上需要一个替代方案,* 较长 * 的单词优先,以便从字符串的其余部分中的较短单词中获益,因此你不能假设第一个成功对应于最优解。循环必须继续进行迭代,只有当循环完成时,您可以知道哪个有效选项是最佳选项。下面是更正后的代码: