LintCode 415.有效回文串

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 261 阅读时长 ≈ 1 分钟

题意

给定一个字符串，判断其是否为一个回文串。只包含字母和数字，忽略大小写。

注意事项

你是否考虑过，字符串有可能是空字符串？这是面试过程中，面试官常常会问的问题。

在这个题目中，我们将空字符串判定为有效回文。

样例

"A man, a plan, a canal: Panama" 是一个回文。

"race a car" 不是一个回文。

思路

这道题的思路很简单，先把给定字符串预处理一下，先只选择其中的字母和数据，再全部变成小写（大写），然后根据回文串的性质左右两边进行比较即可。

坑点在于题意中的注意事项说的，如果是空串的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    """
    @param s: A string
    @return: Whether the string is a valid palindrome
    """
    def isPalindrome(self, s):
        # edge condition
        if s == "":
            return True
        # pre-process
        real = [ch.lower() for ch in s if ch.isalnum()]
        # solve
        i = 0
        j = len(real) - 1
        while i <= j:
            if real[i] != real[j]:
                return False
            i += 1
            j -= 1
        return True