LintCode 415.有效回文串

题意

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

注意事项

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

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

样例

"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
请博主喝杯咖啡~
0%