0125._valid_palindrome.md

Navigation

Links:

1. https://leetcode.com/problems/valid-palindrome/
2. https://leetcode-cn.com/problems/valid-palindrome/

Solution 1 Python API

时间复杂度O(N)，空间复杂度O(N)

class Solution:
    def isPalindrome(self, s):
        s = [e.lower() for e in s if e.isalnum()]
        return s == s[::-1]

---

class Solution(object):
    def isPalindrome(self, s):
        s = filter(str.isalnum, str(s))
        s = s.lower()
        return s == s[::-1]

Solution 2 双指针

时间复杂度O(N)，空间复杂度O(1)

class Solution:
    def isPalindrome(self, s):
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            
            while l < r and not s[r].isalnum():
                r -= 1
            
            if s[l].lower() != s[r].lower():
                return False

            l += 1
            r -= 1

        return True

---

Go

package main

import "strings"

func isPalindrome(s string) bool {
	s = strings.ToLower(s)
	left, right := 0, len(s)-1

	for left < right {
		for left < right && !isChar(s[left]) {
			left++
		}

		for left < right && !isChar(s[right]) {
			right--
		}

		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

func isChar(c byte) bool {
	if ('a' <= c && c <= 'z') || ('0' <= c && c <= '9') {
		return true
	}

	return false
}

---

package main

import "strings"

func isPalindrome(s string) bool {
	s = strings.ToLower(s)
	left, right := 0, len(s)-1

	for left < right {
		for left < right && !isChar(s[left]) {
			left++
		}

		for left < right && !isChar(s[right]) {
			right--
		}

		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

const alphaNums = "abcdefghijklmnopqrstuvwxyz0123456789"

func isChar(b byte) bool {
	if !strings.Contains(alphaNums, string(b)) {
		return false
	}

	return true
}

Solution 3 正则

class Solution(object):
    def isPalindrome(self, s):
        bt = '[a-zA-Z0-9]+'
        m = re.findall(bt, s)
        m = ''.join(m).lower()
        
        return m == m[::-1]