未分類

Longest Palindrome

Go, HashTable, LeetCode

Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:

Assume the length of given string will not exceed 1,010.

For Example:

1
2
3
4
5
6
7
8
Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
提示 解題應用
HashTable HashMap

Default:

1
2
3
func longestPalindrome(s string) int {
}

解答思路:

如果要知道最長回文的長度，首先要知道回文的特色，通常就是兩兩對稱，換句話說就是兩個相同的為一組，而最中間的有可能一個落單，也有可能一樣是一組相同的值，利用這個大多數都是對稱兩個相同為一組的特性，只要找出像這樣相同的共有幾對，最後再看看有沒有剩下落單的值，就可以很容易找出最長回文的長度。

程式碼解說:

因為要確定是否存在一組相同的字串，一開始先初始化一hashmap，key值拿來存字元的rune值而value則隨意，這邊也拿來存字元的rune值，接著開始遍歷字串中的每個字元，如果該字元存在在hashmap之中，就將該字元從hashmap中移除，並且將結果長度+2(一組2個)，如果該字元不存在或者已經找到成對而被移除了，就再一次放入hashmap之中直到出現下一個相同的字元，最後在結束遍歷之後檢查hashmap中有沒有剩下落單的字元，如果有就將任其一拿來當作回文最中間的值，此時回傳長度+1，若沒有則直接將長度回傳即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var length int
hashMap := make(map[rune]rune)
for _, v := range s {
	_, ok := hashMap[v]
	if ok {
		delete(hashMap, v)
		length = length + 2
	} else {
		hashMap[v] = v
	}
}
if len(hashMap) > 0 {
	return length + 1
}
return length

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func longestPalindrome(s string) int {
	var length int
	hashMap := make(map[rune]rune)
	for _, v := range s {
		_, ok := hashMap[v]
		if ok {
			delete(hashMap, v)
			length = length + 2
		} else {
			hashMap[v] = v
		}
	}
	if len(hashMap) > 0 {
		return length + 1
	}
	return length
}

總結:

要找出一字串中能組出最長回文的長度，首先要知道回文的特色，通常就是兩個相同的為一組對稱，而最中間的有可能一個落單，也有可能一樣是一組相同的值，利用這個大多數都是對稱兩個相同為一組的特性，只要找出相同的共有幾對，最後再看看有沒有剩下落單的值，就可以很容易找出最長回文的長度。

分享到