英文:
Leetcode "Decode Ways" problem and recursion error
问题
在您提供的代码中，导致递归无限的原因是代码中的一些逻辑错误，特别是在以下行：
if idx > 1 and s[idx-1] not in "12" and s[idx] == "0":
return 0
这行代码中，您检查前一个字符是否不是'1'或'2'，并且当前字符是否是'0'。如果满足这两个条件，您返回0，即递归终止。然而，这行代码可能包含一个错误，因为您的意图可能是希望当前字符为'0'时，只有前一个字符是'1'或'2'时才返回0。在当前的代码中，如果前一个字符不是'1'或'2'，而当前字符是'0'，它会立即返回0，导致递归不再继续。
为了修复这个问题，您可以将条件更改为：
if idx > 0 and s[idx-1] not in "12" and s[idx] == "0":
return 0
这将仅在前一个字符是'1'或'2'且当前字符是'0'时返回0，而不会在前一个字符不是'1'或'2'时返回0。
修复了这个错误后，您的递归函数应该正常工作，不再导致无限递归。
英文:
I am trying to solve the Leetcode Decode Ways problem (https://leetcode.com/problems/decode-ways/). Consider a string with upper case elements from the English alphabet represented by numbers.
So A maps to 1, B maps to 2, and so on until Z maps to 26. Given a string of numbers, how many ways can one decode it to a string of alphabets?
For example, 11106 can be mapped into:
"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because 06 cannot be mapped into F since 6 is different from 06.
I run into a maximum recursion depth error in Python, even for very short input strings. My solution is below:
def numDecodings(s):
## Case of empty string
if len(s)== 0:
return 1
## Error cases if a zero is in a weird place
for idx, i in enumerate(s):
if idx == 0 and s[idx]=="0":
return 0
if idx > 1 and s[idx-1] not in "12" and s[idx]==0:
return 0
## Recursion
def subProblem(substring):
if len(substring) == 1:
res = 1
else:
res = subProblem(substring[1:])
if (len(substring) > 1) and (substring[0] == "1") or (substring[0] == "2" and (substring[1] in "0123456")):
res += subProblem(substring[2:])
return res
return subProblem(s)
What is causing the unbounded recursion?
答案1
得分: 2
你没有考虑到substring为空的情况。
因此，subProblem()无限地以空字符串作为参数调用自身。
英文:
You aren't accounting for the case when substring is empty.
Therefore subProblem() endlessly calls itself with an empty string as an argument.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论