电话号码的字母组合

题目描述

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

func letterCombinations(digits string) []string {
    // 队列求解
    if len(digits) == 0{
        return []string{}
    }
    result := []string{""}
    number := map[rune]string{
        '2': "abc",
        '3': "def",
        '4': "ghi",
        '5': "jkl",
        '6': "mno",
        '7': "pqrs",
        '8': "tuv",
        '9': "wxyz",
    }
    for _,digit := range digits{
        if digit == '1'{
            continue
        }
        length := len(result)
        for i := 0;i < length;i++{
            str := result[0]
            result = result[1:]
            for _,end := range number[digit]{
                result = append(result,str+string(end))
            }
        }
    }
    return result
}

解题思路

Ⅰ

天才般的想法——队列

var m = map[byte][]string{
	'2': []string{"a", "b", "c"},
	'3': []string{"d", "e", "f"},
	'4': []string{"g", "h", "i"},
	'5': []string{"j", "k", "l"},
	'6': []string{"m", "n", "o"},
	'7': []string{"p", "q", "r", "s"},
	'8': []string{"t", "u", "v"},
	'9': []string{"w", "x", "y", "z"},
}

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

	ret := []string{""}

	// 让digits中所有的数字都有机会进行迭代。
	for i := 0; i < len(digits); i++ {
		temp := []string{}
		// 让ret中的每个元素都能添加新的字母。
		for j := 0; j < len(ret); j++ {
			// 把digits[i]所对应的字母，多次添加到ret[j]的末尾
			for k := 0; k < len(m[digits[i]]); k++ {
				temp = append(temp, ret[j]+m[digits[i]][k])
			}
		}

		ret = temp
	}

	return ret
}

Ⅱ

回溯

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    // 数字字母映射
    mp := map[string]string{
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }
    var ans []string
    var dfs func(int, string)

    // DFS函数定义
    dfs = func(i int, path string) {
        if i >= len(digits) {
            ans = append(ans, path)
            return
        }

        for _, c := range mp[string(digits[i])] {
            dfs(i + 1, path + string(c))
        }
    }
    // 执行回溯函数
    dfs(0, "")
    return ans
}

题解

如代码

总结

• 熟悉回溯
• 队列的巧妙使用