计算回文的递归函数

Question

我知道这个问题已经被问过很多次了，但是我的问题有点不同。这个任务要求我不验证一个字符串是否是回文——而是验证一个字符串中有多少回文（返回为“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]

我只是很难把它转换成递归函数。感谢所有帮助！

Answer 1

我有一个递归的解决方案，但它再次计算一些值，这可以通过动态编程（记忆化）来克服。如有任何建议，将不胜感激。下面是递归的伪代码。

Check whether the string from 'start' index to 'end' index is a palindrome if yes -> inc. the answer and then
recursively check for other strings by removing first and last character from the current string

    import numpy as np
    #initializing dp array with zeros
    dp = np.zeros(shape = (len(st) , len(st))

    def CountPalindromes(st , start, end):
        if(dp[start][end] == 1): return 0
        flag = checkIfTheStringIsPalindrome(st , start, end)
        ans = 0
        if(flag): ans = 1
        dp[start][end] = 1
        if(start < end):
            return ans + CountPalindromes(st , start, end-1) + CountPalindromes(st , start+1 , end)
        else: return ans


     answer = CountPalindromes(st , 0 , len(st)-1)
     print(answer)

在上面的代码中，许多字符串将被重新检查，这将增加计数。为了解决这个问题，dp数组用于跟踪已经计算的子问题

Answer 2

我想我成功了！看看我的递归实现，它可以在字符串中找到所有回文，在我看来，这并不是解决它的最干净的方法（任何让它更简单的建议都会受到欢迎），请随意询问您不清楚的问题：

found = []
def count_palindrome(m_str, start, end, orig_len):
    if len(m_str)<2:
        return
    elif m_str == m_str[::-1]:
        if (start, end) not in found:
            found.append((start, end))
            if len(m_str)<orig_len:
                return
    counter = count_palindrome(m_str[:-1], start, end-1,  orig_len)
    counter = count_palindrome(m_str[1:], start+1, end, orig_len)

str_to_work_on = "acac"
count_palindrome(str_to_work_on, 0, len(str_to_work_on), len(str_to_work_on))
for indices in found:
    print(str_to_work_on[indices[0]:indices[1]])

输出：

aca
cac

# I tried it on more complex examples as well and it seems to work fine for my eyes,
# try to challenge it by giving extra complex examples and examine the results.
# let me know if you find something which not work as you expect