17. 电话号码的字母组合

leecode原题

题目

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

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

示例

示例 1:

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入：digits = ""
输出：[]

示例 3:

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

解题思路

思路

跟77-组合有所不同，但是也是相应的变种，详细参阅:代码随想录

实现

源码

var (
    letterMap = [10]string{
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz", // 9
    }
    s   = make([]rune, 0)   //记录临时结果
    res = make([]string, 0) //记录全局结果
)

func backtracking(digits string, index int) { //index代表遍历到digits的第几个字母，也代表深度
    if index == len(digits) {
        res = append(res, string(s))
        return
    }
    digit := digits[index] - '0' // 将index指向的数字转为int, 比如digits为"23", index为0的情况，去代表取出2对应的字符
    letters := letterMap[digit]  // 取数字对应的字符集
    for i := 0; i < len(letters); i++ {
        s = append(s, rune(letters[i]))
        backtracking(digits, index+1)
        s = s[:len(s)-1]
    }
}

func letterCombinations(digits string) []string {
    s = make([]rune, 0)
    res = make([]string, 0)
    if digits == "" {
        return res
    }
    backtracking(digits, 0)
    return res
}