17.电话号码的字母组合

算法

发布日期: 2023-09-13

更新日期: 2024-03-13

文章字数: 736

阅读时长: 3 分

问题

传送门：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

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

思路

如何找到全部的字母组合呢？其实很明显此题可以使用深度优先遍历（DFS）。我们可以将字母组合看做不同的状态，用当前选取到的数字在字符串digits中的索引todo和已经组合出来的字符串done来表示一个状态；接下来考虑如何进行状态的搜索DFS(string done, int todo, string digits)。

为了方便编程，建立数字字符到字母字符的哈希映射表mps，对于当前需要考虑的数字$digits[todo]$，它对应的字符集为$mps[digits[todo]]$；遍历其中的每一个字符ch，将其加入已经组合出来的字符串done中，且将todo加一，即可得到新的状态：DFS(done+ch, todo+1, digits)。

深度优先遍历搜索树

边界条件

进行深度优先搜索时，必须给出明确的边界条件，它正是搜索到的终止状态。搜索到这个状态时，便可以结束当前的搜索路径，而在程序运行中表现为递归结束，返回上一层函数。

显然，

当索引todo=n（n为digits长度）时，搜索到终止状态，搜索结束，将当前组合出来的字符串done加入向量保存下来。

代码

class Solution {
public:
    map<char, string> mps = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };
    vector<string> res;
    void DFS(string done, int todo, string digits) {
        if(todo == digits.size()) {
            res.push_back(done);
            return;
        }
        string str = mps[digits[todo]];
        for(char ch:str) {
            DFS(done+ch, todo+1, digits);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits == "")    return res;
        string temp = "";
        DFS(temp, 0, digits);
        return res;
    }
};