Backtracking - 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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.

思路：

非常典型的dfs回溯法求所有解问题，因为问题可以画出一个递归树。做法就是递归求解字符串的每一位，枚举所有可能的组合。

代码：

go：

var dict = [][]string{
    {},
    {},
    {"a", "c", "b"},
    {"d", "e", "f"},
    {"g", "h", "i"},
    {"j", "k", "l"},
    {"m", "n", "o"},
    {"p", "q", "r", "s"},
    {"t", "u", "v"},
    {"w", "x", "y", "z"},
}

func letterCombinations(digits string) []string {
    var res []string
    if digits == "" || len(digits) == 0 {
        return res
    }
	
    dfs(digits, 0, "", &res)
    return res
}

func dfs(digits string, index int, temp string, res *[]string) {
    if index == len(digits) {
        *res = append(*res, temp)
        return
    }
    
    idx := digits[index] - '0'
    for _, c := range dict[idx] {
        temp = temp + c
        dfs(digits, index+1, temp, res)
        temp = temp[0:len(temp)-1]
    }
}