未分類

Keyboard Row

Go, HashTable, LeetCode

Keyboard Row

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

For Example:

1
2
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

  1. You may use one character in the keyboard more than once.
  2. You may assume the input string will only contain letters of alphabet.
提示 解題應用
HashTable HashMap

Default:

1
2
3
func findWords(words []string) []string {
}

解答思路:

一開始在準備上稍為麻煩，要將鍵盤上的每一列存到hashmap之中，其中key為該字母而value則是鍵盤上該列數，而準備完成後就已經完全大多數的工作了，剩下的就是一一核對每個單字中的每個字母是否為同一列，如果發現不為同一列的字母就直接換檢查下一個單字，最後檢查完畢即可回傳。

程式碼解說:

一開始先存好鍵盤上的每一列到字串之中，接著再各別以一回圈將其儲至hashmap之中，其中key為該字母而value則是鍵盤上該列數，開始一以迴圈遍歷陣列中的每個單字，再進下一層的巢狀迴圈準備再遍歷每個單字中的每個字母前，先將該單字中的所有字母轉為小寫，接著取出第一個字母到hashmap之中查看該字母為鍵盤上的哪一列，最後才開始檢查單中中的字母，當該字母不等於先查所查的列數時，將先前暫存查詢的列數存為-1並跳開迴圈繼續檢查下一個單字，而如果在離開迴圈後暫存值不等於-1表示該單字全由同列字母儲存，此時就將單字放入結果之中，檢查完所有的單字後回傳結果

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
29
30
var tmp int
var wordLow string
var result []string
row1 := "qwertyuiop"
row2 := "asdfghjkl"
row3 := "zxcvbnm"
hashMap := make(map[rune]int)
for _, v := range row1 {
	hashMap[v] = 1
}
for _, v := range row2 {
	hashMap[v] = 2
}
for _, v := range row3 {
	hashMap[v] = 3
}
for _, word := range words {
	wordLow = strings.ToLower(word)
	tmp = hashMap[rune(wordLow[0])]
	for _, char := range wordLow[1:] {
		if hashMap[char] != tmp {
			tmp = -1
			break
		}
	}
	if tmp != -1 {
		result = append(result, word)
	}
}
return result

完整程式碼:

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
29
30
31
32
func findWords(words []string) []string {
	var tmp int
	var wordLow string
	var result []string
	row1 := "qwertyuiop"
	row2 := "asdfghjkl"
	row3 := "zxcvbnm"
	hashMap := make(map[rune]int)
	for _, v := range row1 {
		hashMap[v] = 1
	}
	for _, v := range row2 {
		hashMap[v] = 2
	}
	for _, v := range row3 {
		hashMap[v] = 3
	}
	for _, word := range words {
		wordLow = strings.ToLower(word)
		tmp = hashMap[rune(wordLow[0])]
		for _, char := range wordLow[1:] {
			if hashMap[char] != tmp {
				tmp = -1
				break
			}
		}
		if tmp != -1 {
			result = append(result, word)
		}
	}
	return result
}

總結:

要檢查一陣列中的數個單字有哪些由鍵盤上的同的列字母所組成，將鍵盤上的每一列存到hashmap之中，其中key為該字母而value則是鍵盤上該列數，最後一一核對每個單字中的每個字母是否為同一列，如果發現不為同一列的字母就直接換檢查下一個單字，最後檢查完畢即可回傳。

分享到