未分類

First Unique Character in a String

Go, LeetCode, String

First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

For Examples:

1
2
3
4
5
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.

Note:

You may assume the string contain only lowercase letters.

提示 解題應用
String HashTable

Default:

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

解答思路:

這題要你找出字串中獨一無二的字母，並且回傳其index值，基本上一樣採用hashmap來實作，key值為該字母，value則為index值，當發現其字母已經存在於hashmap之中表示重覆，將原本index值以-1來覆蓋，最後遍歷結束只要再次檢查找出值不為-1的value值，其key值就是獨一無二的字母。

程式碼解說:

一開始先將回傳的預設值設為-1，再來初始化hashmap，其中key為字母的rune值而value則是儲存index值，接著開始以迴圈遍歷整個字串的字母，如果該字母不存在就將其字母與index值放入hashmap之中，如果存在表示不為獨一無二的字母，將原本的index值取代為-1，最後遍歷結束只要再次以迴圈確認每個hashmap的value是否存在不為-1的結果，只不過這邊要注意到的是因為字串可能存在一個以上獨一無二的字母，所以要回傳index值為最小的字母，偏偏hashmap儲存時是無序的狀況，還必須要多個判斷找出最小的index值，另外因為初始化回傳值為-1會永遠最小，所以再發現value不為-1時，記得要先將回傳值給蓋掉才開始找最小index值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
result := -1
hashMap := make(map[rune]int)
for i, v := range s {
	_, ok := hashMap[v]
	if !ok {
		hashMap[v] = i
	} else {
		hashMap[v] = -1
	}
}
for _, value := range hashMap {
	if value != -1 && (result == -1 || value < result) {
		result = value
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func firstUniqChar(s string) int {
	result := -1
	hashMap := make(map[rune]int)
	for i, v := range s {
		_, ok := hashMap[v]
		if !ok {
			hashMap[v] = i
		} else {
			hashMap[v] = -1
		}
	}
	for _, value := range hashMap {
		if value != -1 && (result == -1 || value < result) {
			result = value
		}
	}
	return result
}

總結:

要出字串中獨一無二的字母並回傳index值，基本上一樣採用hashmap來實作，key值為該字母，value則為index值，當發現其字母已經存在於hashmap之中表示重覆，將原本index值以-1來覆蓋，最後遍歷結束只要再次檢查找出值不為-1的value值，其key值就是獨一無二的字母。

分享到