azalea says

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

回文(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个方法快。

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

bioinformatics programming python string · Tweet Edit