首页 > itarticle > l125 valid palindrome

l125 valid palindrome

admin 11月 13, 2020 0

题目描述

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.

解题思路

使用low和high两个指针进行判断
如果遇到非alphanumeric字符，进行跳过处理

Go实现

package main

import (
    "fmt"
)

func (char uint8) bool  {
    if (char >= 'A' && char <='Z') || (char>='a' && char<='z')||
        (char >='0' && char<='9') || char=='_'{
        return true
    }else{
        return false
    }
}

func lower(char uint8) uint8 {
    if char >='a' && char<='z' {
        char = char-'a'+'A'
    }

    return char
}

func isPalindrome(s string) bool {
    if len(s) == 0 || len(s) == 1{
        return true
    }

    low:=0
    high := len(s)-1

    for low<high  {
        if !isAlphanumeric(s[low]) {
            low++
        }else if !isAlphanumeric(s[high]) {
            high--
        }else {
            if lower(s[low]) == lower(s[high])  {
                low++
                high--
            }else{
                return false
            }
        }
    }
    return true
}

func main()  {
    
    //fmt.Println(isPalindrome("race a car"))
    fmt.Println(isPalindrome("0P"))
    fmt.Println(isPalindrome("a."))
    //fmt.Println(len("."))
}

Python实现

使用基本比较

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True

        low = 0
        high = len(s) - 1

        while low < high:
            if not str.isalnum(str(s[low])):
                low += 1
            elif not str.isalnum(str(s[high])):
                high -= 1
            else:
                if str.lower(str(s[low])) == str.lower(str(s[high])):
                    low += 1
                    high -= 1
                else:
                    return False
        return True

遇到的错误信息:

1
2
3

Runtime Error Message:
Line 14: TypeError: descriptor 'isalnum' requires a 'str' object but received a 'unicode'
Last executed input: "a."

使用库函数


class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        newString = re.sub("[^0-9a-zA-Z]+", "", s)
        return newString.lower() == newString.lower()[::-1]