python判断字符串是否是回文结构

Dec 11, 2010

回文（Palindrome），就是一个序列（如字符串）正着读反着读是一样的。生物信息学上最常见的就是转录因子在DNA上的结合位点通常都是回文结构。

个么如何判断一个字符串是回文结构呢？在MIT Introduction to CS and Programming Lec 4 (39:38) 里，介绍了递归的方法：

def isPalindrome(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and isPalindrome(s[1:-1])

其实完全可以用循环实现，复杂度是一样的：

def isPalindrome1(s):
    for i in range(len(s))/2:
        if not s[i] == s[len(s)-i-1]:
            return False
    return True

不过其实我们都被忽悠啦，在Python里可以很容易的从回文的定义来判断，就是字符串的倒序和字符串本身是一样的话，就是回文。

def isPalindrome2(s):
    return s == s[::-1]

以上的实现复杂度也是O(n)的，不过是python内部用C语言实现的，猜测会比前2个方法快。

总之这又是一个递归的失败的例子，斐波那契数列是另一个，递归的方法比循环的方法要慢很多。唯一我知道的递归是最适用的方法的就是汉诺塔了。跑题了，不多说了。。

azalea says