未分類

Letter Combinations of a Phone Number

Backtracking, Go, LeetCode, String

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

1
2
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

提示 解題應用
Backtracking Recursive
String 規律觀查

Default:

1
2
3
func letterCombinations(digits string) []string {
}

解答思路:

這題沒有什麼技巧，因為所有的狀況都需要一一列出，唯一要注意的是給予的數字長度都不一定，因此沒辦法單靠超多層的巢狀迴圈來搞定，所以需要一個方式來遍歷並組合所有可能，如果題目是用二元樹也表示，也許可以從葉子節點一個個合併回根部來取得所有情況，不過這邊不是以節點來處理資料，所以就用遞回的方式來將每次組合出的結果往下傳並再次做排列組合，直到所有的號碼都遍歷為止才回傳所有組合出的結果。

程式碼解說:

一開始因為需要知道電話上數字與英文字母的對照，因此要將其關係分別存儲至hashmap之中，不過由於數字的參數給的也是字串的型別，所以key值同為字串型別的數字號碼，而value則是對應的英文字母字串，接著便傳入遞回之中，第一個參數是尚未遍歷的數字，第二個則是數字與英文字母的對照表，最後是目前已組合出的所有結果(最初當然為空的字串陣列)

1
2
3
4
5
6
7
8
9
10
11
12
func letterCombinations(digits string) []string {
	phoneNum := make(map[string]string)
	phoneNum["2"] = "abc"
	phoneNum["3"] = "def"
	phoneNum["4"] = "ghi"
	phoneNum["5"] = "jkl"
	phoneNum["6"] = "mno"
	phoneNum["7"] = "pqrs"
	phoneNum["8"] = "tuv"
	phoneNum["9"] = "wxyz"
	return combine(digits, phoneNum, []string{})
}

接下來便是遞回內容的重頭戲，如果尚未遍歷的數字字串為空，此時表示已經完全遍歷所有數字並找出所有的結果，直接回傳已組合出的所有結果至上層，如果還有數字存在，就再取第一個數字並放入hashmap之中做對照找出對應的字母組，以利接下來從回圈一一取出每個字母來再次做組合，將每字母從rune值轉回字串後，如果已組合出的所有結果為空，表示此為第一個數字才剛始，此時就只要直接將字母一一放入結果之中即可，而如果已組合出的結果存在，就需要將已組合的結果與字母組再次排列組合，這邊是一一取出每個已組合的結果，並將先前字母組中的字母放入已組合的字串後頭，最後再放回結果之中，直到已組合的結果與字母組全部組合完畢，就將已遍歷的第一個數字去除，連同其餘結果帶入參數並再次遞回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func combine(digits string, phoneNum map[string]string, ready []string) []string {
	var str string
	var result []string
	if len(digits) == 0 {
		return ready
	}
	digit := string(digits[0])
	for _, v := range phoneNum[digit] {
		str = string(v)
		if len(ready) == 0 {
			result = append(result, str)
		} else {
			for _, r := range ready {
				str = r + str
				result = append(result, str)
				str = string(v)
			}
		}
	}
	return combine(digits[1:], phoneNum, 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
33
func letterCombinations(digits string) []string {
	phoneNum := make(map[string]string)
	phoneNum["2"] = "abc"
	phoneNum["3"] = "def"
	phoneNum["4"] = "ghi"
	phoneNum["5"] = "jkl"
	phoneNum["6"] = "mno"
	phoneNum["7"] = "pqrs"
	phoneNum["8"] = "tuv"
	phoneNum["9"] = "wxyz"
	return combine(digits, phoneNum, []string{})
}
func combine(digits string, phoneNum map[string]string, ready []string) []string {
	var str string
	var result []string
	if len(digits) == 0 {
		return ready
	}
	digit := string(digits[0])
	for _, v := range phoneNum[digit] {
		str = string(v)
		if len(ready) == 0 {
			result = append(result, str)
		} else {
			for _, r := range ready {
				str = r + str
				result = append(result, str)
				str = string(v)
			}
		}
	}
	return combine(digits[1:], phoneNum, result)
}

總結:

在傳統手機上每個數字也代表數個英文字母與特殊符號，給一串數字找出該數能表示的所有可能，最簡單的方式就是用遞回將每次組合出的結果往下傳並再次做組合，直到所有的號碼都遍歷為止才回傳所有組合出的結果。

分享到