LeetCode 17 电话号码的字母组合

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

解题：

写一个映射表，然后把每一个数字拆分成字母组成的数组，后面数字代表的字母分开跟到前面的数组后面

代码

func letterCombinations(digits string) []string {
    table := map[byte]string{
        '2': "abc",
        '3': "def",
        '4': "ghi",
        '5': "jkl",
        '6': "mno",
        '7': "pqrs",
        '8': "tuv",
        '9': "wxyz",
    }
    var result []string
    for i := range digits {
        tmp := result
        result = []string{}
        for j := range table[digits[i]] {
            if i == 0 {
                result = append(result, string(table[digits[i]][j]))
                continue
            }
            for k := range tmp {
                result = append(result, tmp[k]+string(table[digits[i]][j]))
            }
        }
    }
    return result
}

官方解答：回溯

var phoneMap map[string]string = map[string]string{
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}


var combinations []string


func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    combinations = []string{}
    backtrack(digits, 0, "")
    return combinations
}


func backtrack(digits string, index int, combination string) {
    if index == len(digits) {
        combinations = append(combinations, combination)
    } else {
        digit := string(digits[index])
        letters := phoneMap[digit]
        lettersCount := len(letters)
        for i := 0; i < lettersCount; i++ {
            backtrack(digits, index + 1, combination + string(letters[i]))
        }
    }
}