Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

思路

判断一个字符串是否为回文。注意，空字符串也是回文。

在Python当中，如果对字符串频繁采取+操作，会非常耗时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = s.lower()
        alphabet = "abcdefghijklmnopqrstuvwxyz0123456789"
        res = ""
        for i in s:
            if (i in alphabet):
            	# 最花时间的操作是在这儿对于字符串的操作
                # 在python，list.append()的时间复杂度为O(1)，可以考虑转换为list
                res += i
        
        length = len(res)
        
        for i in range(length):
            if (res[i] != res[-(i+1)]):
                return False
        return True

利用接下来的代码，便不会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = s.lower()
        #alphabet = "abcdefghijklmnopqrstuvwxyz0123456789"
        res = []
        for i in s:
            if (ord("a") <= ord(i) <= ord("z") or ord("0") <= ord(i) <= ord("9")):
                res.append(i)
        
        length = len(res)
        i = 0
        j = length - 1
        while ( i < j ):
            if (res[i] != res[j]):
                return False
            i += 1
            j -= 1
        return True