未分類

Valid Palindrome

Go, LeetCode, Modify, String, TwoPointers

Valid Palindrome

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

For example:

1
2
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
提示 解題應用
TwoPointers String

Default:

1
2
3
func isPalindrome(s string) bool {
}

解答思路:

(此題思路有修正，建議看完直接拉到最底下參考修正的部分)

這題給你一段字串來要確認是否回文，而且這段字串也會有其它符號存在，不過我想如果曾寫過程式的人一定有摸過ASCII，如此一來只要注意大小寫、數字及ASCII的範圍就可以很輕易的完成。

程式碼解說:

一開始先初始兩個字串，一個用來儲存去除掉符號之後的原始字串，另一個則是存放原始字串的相反結果，將給予的字串先全部轉成小寫，方便我們在一個個字元取出時好判斷，畢竟回文也是無視大小寫，至於判斷就利用取出字串的字元在go中會自動轉為rune值(int)，是否介於97~122之間(a~z)或48~57之間(0~9)，然後將一個個字元分別從後頭放入新字串(原始字串)與從前頭放入新字串(相反字串)，最後比對這兩個字串是否相同便等同判斷是否回文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var origin string
var reverse string
s = strings.ToLower(s)
for _, v := range s {
	if v >= 97 && v <= 122 || v >= 48 && v <= 57 {
		origin = origin + string(v)
		reverse = string(v) + reverse
	}
}
if origin == reverse {
	return true
} else {
	return false
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func isPalindrome(s string) bool {
	var origin string
	var reverse string
	s = strings.ToLower(s)
	for _, v := range s {
		if v >= 97 && v <= 122 || v >= 48 && v <= 57 {
			origin = origin + string(v)
			reverse = string(v) + reverse
		}
	}
	if origin == reverse {
		return true
	} else {
		return false
	}
}

總結:

字串的回文要注意到大小寫、數字及ASCII的範圍，接著只要用兩個字串儲存正、反結果後對比即可。

修正:

同時從整個字串的頭與尾遍歷，如果頭尾任一端遇上非英文字母的字元，該端就不斷的往前(或往後)找到英文字母為止，接著才進行比較兩端的字母是否相同，如果整串都只有特殊字元，頭的那端會一口氣遍歷到底，此時就直接回傳true，最後如果頭端的位置大於尾端表示檢查完畢，此時才回傳true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func isPalindrome(s string) bool {
	s = strings.ToLower(s)
	var strFront rune
	var strRear rune
	front := 0
	rear := len(s) - 1
	for front < rear {
		strFront = rune(s[front])
		strRear = rune(s[rear])
		for !(strFront >= 97 && strFront <= 122 || strFront >= 48 && strFront <= 57) {
			front++
			if front == len(s) {
				return true
			}
			strFront = rune(s[front])
		}
		for !(strRear >= 97 && strRear <= 122 || strRear >= 48 && strRear <= 57) {
			rear--
			strRear = rune(s[rear])
		}
		if strFront != strRear {
			return false
		}
		front++
		rear--
	}
	return true
}
分享到