0125. Valid Palindrome

題目

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Example 2:

Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. Example 3:

Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

1 <= s.length <= 2 * 105 s consists only of printable ASCII characters.

題目大意

解題思路

左右指針

Big O

時間複雜 : O(n) 空間複雜 : O(1)

來源

• https://leetcode.com/problems/valid-palindrome
• https://leetcode.cn/problems/valid-palindrome

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0125.Valid-Palindrome/main.go

package validpalindrome

import (
    "strings"
    "unicode"
)

// 時間複雜 O(), 空間複雜 O()
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 unicode.IsLetter(rune(c)) || unicode.IsDigit(rune(c)) {
        return true
    }
    return false
}

func isCharAZ09(c byte) bool {
    if ('a' 

Benchmark

goos: darwin
goarch: amd64
pkg: LeetcodeGolang/Leetcode/0125.Valid-Palindrome
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
BenchmarkIsPalindrome-8                  3840048               552.2 ns/op            32 B/op          1 allocs/op
BenchmarkIsPalindromeStrBuilder-8        3164848               439.0 ns/op            88 B/op          4 allocs/op
PASS
ok      LeetcodeGolang/Leetcode/0125.Valid-Palindrome   5.242s