# 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.

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]
}
}
``````

Nothing just happens, it's all part of a plan.