Valid Palindrome

Question

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

Notice

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.

Example

"A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

Solution 1

首先可以想到的方法是，通过循环过滤掉非字母数字的特殊字符，得到一个新的字母数字的字符串，然后对这个字符串进行回文检测。

class Solution:
    # @param {string} s A string
    # @return {boolean} Whether the string is a valid palindrome
    def isPalindrome(self, s):
        # Write your code here
        if s == '' or len(s) == 1:
            return True
        str = ''

        for i in range(len(s)):
            if s[i].isalpha() or s[i].isdigit():
                str += s[i].lower()

        n = len(str)

        for i in range(n):
            if str[i] != str[n - i - 1]:
                return False
        return True

Solution 2

由于回文的判断，基本上都是两个指针的方法，可以定义这样的两个指针，开始， 结束指针，然后左右移动，如果是特殊字符则忽略，如果是字母数字则进行判定，两个指针的思想可以从quick sort 中的partioning 算法中得来。

class Solution:
    # @param {string} s A string
    # @return {boolean} Whether the string is a valid palindrome
    def isPalindrome(self, s):
        # Write your code here
        start, end = 0, len(s) - 1

        while start < end:
            while start < end and not s[start].isalpha() and not s[start].isdigit():
                start += 1
            while start < end and not s[end].isalpha() and not s[end].isdigit():
                end -= 1
            if start < end and s[start].lower() != s[end].lower():
                return False
            else:
                start += 1
                end -= 1
        return True