无切片和循环的递归函数回文检查

Question

我有一个任务，我必须编写一个 python 代码来检查一个字符串是否是回文，它使用 returns 布尔值的递归函数，但我不允许使用 reversed切片也不是循环，我不允许更改函数格式，这是我的代码，但它 returns 一直如此

def is_palindrome(s):
    res = []
    s = ['']
    if len(s) < 2:
        return True
    else:
        rev_s = is_palindrome(s[1:]) + s[0]
        res.append(rev_s)
        if res == s:
            return True
        return False

Answer 1

您可以检查给定字符串的第一个和最后一个字符是否相同，然后递归检查剩余字符串是否为回文：

def is_palindrome(s):
    return len(s) < 2 or s[0] == s[-1] and is_palindrome(s[1:-1])

Answer 2

我不确定这是否算作 'changing the function format'，但这是我对没有切片的递归版本的尝试：

def is_palindrome(s):
  def is_palindrome_r(i, j):
    if j <= i:
      return True
    if s[i] != s[j]:
      return False
    return is_palindrome_r(i + 1, j - 1)

  return is_palindrome_r(0, len(s) - 1)

内部函数 is_palindrome_r 是采用两个索引 i 和 j 的递归函数。最后一行将这两个索引的初始位置设置为 0（字符串的开头）和 len(s) - 1（字符串的结尾）并继续执行递归逻辑。递归函数有两个退出条件：

if j <= i 我们已经到达回文的中心。如果我们已经做到这一点，我们就知道所有其他字符对都匹配，我们不需要再做任何比较。
如果i和j指向的两个字符不匹配，则肯定不是回文，不需要做没有更多的比较。

否则我们还不知道序列是否完全回文，所以我们将索引向内移动一步 (i + 1, j - 1) 并返回到第 1 步。

Answer 3

没有使用切片，只是通过递归调用维护索引

def is_palindrome(s):
  return helper(s, 0, len(s)-1)

def helper(s, i, j):
  if (i >= j):
    return True
  return s[i] == s[j] and helper(s, i+1, j-1)

Answer 4

如果提到的函数签名def is_palindrome(s)是你老师给的签名那么没问题，也不需要传递任何额外的参数来实现目标。

你的老师（或者给你这个任务的老师很棒）只是想看看你如何处理只有 1 个参数的问题。

The concept is very simple, just change the type of argument (to list with 3 values) in second recursive call.

def is_palindrome(s):
    if type(s) is str:
        l = len(s) 

        if l == 0 or l == 1:
            return True
        else:
            return is_palindrome([s, 0, -1])
    else:
        string, start, end = s # s is list here

        if string[start] != string[end]:
            return False
        else:
            if(start + 1 >= end - 1):
                return True

            return is_palindrome([s, start + 1, end - 1])

def main():
    string1 = "abcba"
    string2 = "abcde"
    string3 = "AxxA"

    print(is_palindrome(string1)) # True
    print(is_palindrome(string2)) # False
    print(is_palindrome(string3)) # True

main();

The following is not what you're looking for but may be you'll be looking for that in future.

>>> def is_palindrome(s):
...     if s == "".join(reversed(s)):
...         return True
...     else:
...         return False
...
>>> is_palindrome("ABA")
True
>>>
>>> is_palindrome("ABC")
False
>>>
>>> is_palindrome("XXZZXX")
True
>>>
>>> is_palindrome("@#7")
False
>>>
>>> is_palindrome("1@#@1")
True
>>>

谢谢。

无切片和循环的递归函数回文检查

Palindrome check with recursive function without slicing and loops

python

recursion

palindrome

python-2.7