未分類

Palindrome Linked List

Go, HashTable, LeetCode, Sort

Palindrome Linked List

Given two strings s and t, write a function to determine if t is an anagram of s.

For example:

1
2
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:

You may assume the string contains only lowercase alphabets.

Follow up:

What if the inputs contain unicode characters? How would you adapt your solution to such case?

提示 解題應用
HashTable HashMap

Default:

1
2
3
func isAnagram(s string, t string) bool {
}

解答思路:

要比較兩個字串是否由相同字母且每個字母都數量都相同所組成，最簡單的方式就是統計此兩個字串的每個字母分別用了哪些又用了多少個，最後比較數量是否一致，要統計這些無序的字母用HashMap就可以達到我們要的目地了。

程式碼解說:

一開始先判斷長度是否一致，不一致肯定不是由相同數量的字母組成，接著就是初始化兩字串所要儲存的hashmap，key值為每個字元的rune值，而value則是統計數量，待第一個迴圈將兩字串的字母全部取出做儲存統計後，最後在用第二個迴圈比較每組key所對應的值是否相同，如果不同就回傳false，直到全數檢查完畢才回傳true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if len(s) != len(t) {
	return false
}
var char rune
sHashMap := make(map[rune]int)
tHashMap := make(map[rune]int)
for i, v := range s {
	char = rune(t[i])
	sHashMap[v] += 1
	tHashMap[char] += 1
}
for key, value := range sHashMap {
	if value != tHashMap[key] {
		return false
	}
}
return true

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}
	var char rune
	sHashMap := make(map[rune]int)
	tHashMap := make(map[rune]int)
	for i, v := range s {
		char = rune(t[i])
		sHashMap[v] += 1
		tHashMap[char] += 1
	}
	for key, value := range sHashMap {
		if value != tHashMap[key] {
			return false
		}
	}
	return true
}

總結:

要比較兩個字串是否由相同字母且每個字母都數量都相同所組成，最快的方式就是將每個字母分別利用hashmap做儲存統計，最後比較兩字串的hashmap每組key與value是否完全一致即可。

分享到