目录
17. 电话号码的字母组合
访问量:146

一、简介

题目:电话号码的字母组合

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

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

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

二、实现

思路:针对每个数字有多个选择,从第一个数字开始,遍历每个case,比如“23”,可构建数组arr,[['a','b','c'],['d','e','f']],要构建一个字符串,需要从数组arr的每个元素中分别任取一位数字即可。


func letterCombinations(digits string) []string {
    if digits == "" || digits == "1" {
        return nil
    }

    // 构建便于遍历的
    numMap := map[byte][]byte{
		'2': []byte{'a', 'b', 'c'},
		'3': []byte{'d', 'e', 'f'},
		'4': []byte{'g', 'h', 'i'},
		'5': []byte{'j', 'k', 'l'},
		'6': []byte{'m', 'n', 'o'},
		'7': []byte{'p', 'q', 'r', 's'},
		'8': []byte{'t', 'u', 'v'},
		'9': []byte{'w', 'x', 'y', 'z'},
	}

	digitsNum := make([][]byte, len(digits))
	for i := 0; i < len(digits); i++ {
		digitsNum[i] = numMap[digits[i]]
	}

    res := make([]string, 0)
    doCombination(digitsNum, []byte{}, &res)

    return res
}

func doCombination(digitsNum [][]byte, curList []byte, res *[]string) {
    if len(digitsNum) == 0 {
        b := make([]byte, len(curList))
        copy(b, curList)

        *res = append(*res, string(b))

        return
    }

    for i :=0; i< len(digitsNum[0]); i++ {
        curList = append(curList, digitsNum[0][i])
        doCombination(digitsNum[1:], curList, res)
        // 回溯
        curList = curList[:len(curList)-1]
    }
}