我知道这个问题已经被问了很多次,但我的问题略有不同。此赋值要求我不验证字符串是否为回文,而是验证一个字符串中有多少回文(返回为“int”)。这应该使用迭代函数和;一个递归函数,但递归部分有问题:(
以下是我的迭代函数代码供参考:
def iterativePalindrome(str, n):
allPalindromes = [[0 for x in range(n)] for y in range(n)]
verify = [[False for x in range(n)] for y in range(n)]
for i in range(n):
verify[i][i] = True
for i in range(n - 1):
if (str[i] == str[i + 1]):
verify[i][i + 1] = True
allPalindromes[i][i + 1] = 1
for iterativeGap in range(2, n):
for start in range(n - iterativeGap):
end = iterativeGap + start;
if (str[start] == str[end] and verify[start + 1][end - 1]):
verify[start][end] = True
if (verify[start][end] == True):
allPalindromes[start][end] = (allPalindromes[start][end - 1] + allPalindromes[start + 1][end] + 1 - allPalindromes[start + 1][end - 1])
else:
allPalindromes[start][end] = (allPalindromes[start][end - 1] + allPalindromes[start + 1][end] - allPalindromes[start + 1][end - 1])
return allPalindromes[0][n - 1]
我只是在把它转换成递归函数方面遇到了困难。非常感谢您的帮助
我有一个递归的解决方案,但它再次计算一些值,这可以通过动态编程(记忆化)来克服。如有任何建议,将不胜感激。 下面是递归的伪代码
在上面的代码中,许多字符串将被重新检查,这将增加计数,为了解决这个问题,使用dp数组跟踪已经计算的子问题
我想我成功了!看看我的递归实现,它在字符串中查找所有回文,在我看来,这不是解决它的最干净的方法(任何使它更简单的建议都会受到欢迎),请随意询问您不清楚的问题:
输出:
相关问题 更多 >
编程相关推荐