17. Alphabetic combinations of telephone numbers

A string containing only the numbers 2-9 that returns all the letter combinations it can represent. The answers can be returned in any order.

The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.

Source: LeetCode link: leetcode-cn.com/problems/le… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The knowledge involved in solving this problem with Go includes:

1. Initialize and use map in Go

Map Official Documents

Maps can be initialized using make or constants:

a := make(map[string]string)
a["key"] = "value"
fmt.Println(a)
b := map[string]string {
    "keyb": "valueb",
}
fmt.Println(b)
Copy the code

2. For loop control

If you get used to a for-range, it’s a lot simpler than for-i. Not only can you iterate over arrays, slices, but you can also iterate over maps, strings. When an argument is not needed, it can be replaced with _.

For arrays: the first parameter represents the index, and the second parameter represents the value. For map: the first parameter indicates the key, and the second parameter indicates the value.

for _, letter := range letters {
	// loop
}
Copy the code

3. Append slice to add elements

Append can add elements to a slice and return the modified slice.

slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)
Copy the code

4. Go pointer:

This is the first time FOR me to use the pointer to Go. It is used in the way of C language, which is basically the operation of **& fetch address, * value **. Not much exposition.

Back to the title, which I personally think has been complicated by the authorities, perhaps to cover the backtracking problem.

Algorithm 1: Three layers are added one by one.

The initialization result := []string{“”} is a line of code that I am very proud of

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	numToLetterMap := map[string]string{
		"2": "abc"."3": "def"."4": "ghi"."5": "jkl"."6": "mno"."Seven": "pqrs"."8": "tuv"."9": "wxyz",
	}
	result := []string{""}
	for _, v := range digits {
		letters := numToLetterMap[string(v)]
		temp := make([]string.0)
		for _, str := range result {
			for _, letter := range letters {
				temp = append(temp, str + string(letter))
			}
		}
		result = temp
	}
	return result
}
Copy the code

Algorithm 2: backtracking (recursive). Draw on the official algorithm logic.

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	numToLetterMap := map[string]string{
		"2": "abc"."3": "def"."4": "ghi"."5": "jkl"."6": "mno"."Seven": "pqrs"."8": "tuv"."9": "wxyz",
	}
	result := []string{}
	backtrack(digits, 0."", &result, numToLetterMap)
	return result
}

func backtrack(d string, index int, combination string, result *[]string, m map[string]string)  {
	if index == len(d) {
		*result = append(*result, combination)
	} else {
		num := string(d[index])
		letters := m[num]
		for i := 0; i < len(letters); i++ {
			backtrack(d, index+1, combination+string(letters[i]), result, m)
		}
	}
}
Copy the code

I have used Go to brush and button 17 questions. I have almost understood the basic knowledge of Go, but the complete Go logic has not been established yet. Therefore, I would like to read some Go books to link the knowledge together.