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