leetcode17：电话号码的字母组合

题目链接

leetcode

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意：1 不对应任何字母。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    回溯法，深度优先搜索

    时间复杂度：O(3^m*4^n)
        其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数。
        当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，
        不同的字母组合一共有 3^m*4^n 种，需要遍历每一种字母组合。
    空间复杂度：O(m + n)
        除了返回值以外，主要取决于哈希表以及回溯过程中的递归调用层数，
        哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m + n。
*/
class Solution_0 {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return res;
        dfs(digits, 0);
        return res;
    }

    void dfs(const string& digits, int start) {
        if (path.size() == digits.size()) {
            res.push_back(path);
            return;
        }

        // 回溯算法框架
        for (int i = start; i < digits.size(); i ++) {
            int index = digits[i] - '0';
            for (char ch : num2str[index]) {
                path.push_back(ch); // 做选择
                dfs(digits, i + 1); // 递归下一层回溯树
                path.pop_back();    // 撤销选择
            }
        }
    }
    
private:
    string num2str[10] = {
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz"
    };
    vector<string> res;
    string path;
};

// 思路同上 
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        string path;
        if (digits.empty()) return res;
        dfs(digits, res, path, 0);
        return res;
    }

    void dfs(const string& digits, vector<string>& res, string path, int start) {
        if (path.size() == digits.size()) {
            res.push_back(path);
            return;
        }

        // 回溯算法框架
        for (int i = start; i < digits.size(); i ++) {
            int index = digits[i] - '0';
            for (char ch : num2str[index]) {
                path.push_back(ch); // 做选择
                dfs(digits, res, path, i + 1); // 递归下一层回溯树
                path.pop_back();    // 撤销选择
            }
        }
    }

private:
    string num2str[10] = {
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz"
    };
};

int main() {
    Solution solution;
    string digits = "23";
    vector<string> combinations = solution.letterCombinations(digits);
    cout << "Letter combinations for " << digits << " are:" << endl;
    for (const string& combination : combinations) {
        cout << combination << " ";
    }
    cout << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   回溯算法：
       使用回溯算法生成所有可能的字母组合。
       回溯算法通过递归模拟所有可能的选择路径，每次选择一个字母加入当前组合，并在递归返回时恢复状态。
   映射表：
       使用一个映射表 phoneMap，将每个数字映射到对应的字母集合。
   递归函数：
       每次从当前数字对应的字母集合中选择一个字母，加入当前组合。
       递归处理下一个数字，直到处理完所有数字。
       将生成的组合加入结果列表。
   结束条件：
       当没有更多的数字需要处理时，将当前组合加入结果列表。

    时间复杂度：O(n*4^n)
        每个数字最多对应4个字母，因此生成所有组合的时间复杂度为 O(4^n)，其中 n 是输入字符串的长度。
        每个组合的生成时间复杂度为 O(n)，因为需要将组合加入结果列表。
        因此，总时间复杂度为 O(n*4^n)。
    空间复杂度：O(n*4^n)
        递归调用栈的深度为 O(n)。
        当前组合 combination 的空间复杂度为 O(n)。
        结果列表 result 的空间复杂度为 O(4^n)，因为需要存储所有组合。
        因此，总空间复杂度为 O(n*4^n)。
*/
func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

	// 电话号码到字母的映射
    phoneMap := map[byte]string{
        '2': "abc", '3': "def",
        '4': "ghi", '5': "jkl", '6': "mno",
        '7': "pqrs", '8': "tuv", '9': "wxyz",
    }
    var result []string

    var dfs func(digits, path string)
    dfs = func(digits, path string) {
        // 如果没有更多的数字，将当前组合加入结果
        if len(digits) == 0 {
            result = append(result, path)
            return
        }
        // 获取当前数字对应的字母
        letters := phoneMap[digits[0]]
        for _, letter := range letters {
            // 递归构建下一个组合
            dfs(digits[1:], path+string(letter))
        }
    }

    // 开始回溯
    dfs(digits, "")
    return result
}

func main() {
	// 测试用例
	testCases := []struct {
		digits   string
		expected []string
	}{
		{
			digits: "23",
			expected: []string{
				"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf",
			},
		},
		{
			digits:   "2",
			expected: []string{"a", "b", "c"},
		},
		{
			digits:   "",
			expected: []string{},
		},
	}

	for i, tc := range testCases {
		fmt.Printf("Test Case %d, Input: digits = %s\n", i+1, tc.digits)
		result := letterCombinations(tc.digits)

		if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}