LC17.电话号码的字母组合

题目

17. 电话号码的字母组合 (Medium)

给定一个仅包含数字 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'] 的一个数字。

---

思路

1. 回溯模板题
2. 脑子里面需要有一张图片，树的结构是如何进行逐层访问的
3. 注意回退

代码

// Created by Albert at 2023/04/06 18:31
// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

package main

import (
	// "bufio"
	"fmt"
	// "os"

	. "github.com/j178/leetgo/testutils/go"
)

// @lc code=begin

func backTrack(digits string, numberToString map[rune]string, curDepth int, ans *[]string, combiantion string) {
    if (curDepth == len(digits)) {
        *ans = append(*ans, combiantion)
        return
    } else {
        digit := digits[curDepth]
        letters := numberToString[rune(digit)]
        for i := 0; i < len(letters); i++ {
            combiantion += string(letters[i])
            backTrack(digits, numberToString, curDepth + 1, ans, combiantion)
            combiantion = combiantion[:len(combiantion) - 1]
        }
    }

}

func letterCombinations(digits string) (ans []string) {
    if (digits == "") {
        return []string{}
    }

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

    backTrack(digits, numberToString, 0, &ans, "")
    return
}

// @lc code=end

func main() {
    // stdin := bufio.NewReader(os.Stdin)
    // digits := Deserialize[string](ReadLine(stdin))
    digits := "234"
    digits = "4"
    ans := letterCombinations(digits)
    fmt.Println("output: " + Serialize(ans))
}