README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
0125. Valid Palindrome	https://leetcode.com/problems/valid-palindrome/	2023-10-13 16:11:00 +0800	2023-10-13 16:11:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	Valid Palindrome			LeetCode Go Easy Valid Palindrome	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

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' <= c && c <= 'z') || ('0' <= c && c <= '9') {
		return true
	}
	return false
}

func IsPalindromeStrBuilder(s string) bool {
	s = strings.ToLower(s)
	strLen := len(s)
	// 將字符轉成小寫, 並濾掉空格和標點符號等字符
	var sb strings.Builder
	for i := 0; i < strLen; i++ {
		c := rune(s[i])
		if unicode.IsLetter(c) || unicode.IsDigit(c) {
			sb.WriteRune(c)
		}
	}

	sbStr := sb.String()

	// 使用雙指針, 一左一右相向而行, 判斷回文
	left, right := 0, len(sbStr)-1
	for left < right {
		if sbStr[left] != sbStr[right] {
			return false
		}
		left++
		right--
	}
	return true
}

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