【LeetCode Hot100 C++】电话号码的字母组合

题目描述

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

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]

题目解析

本题适合用回溯法做，先用散列表存储这些

回溯法

解决一个回溯问题，实际就是一个决策树的遍历问题。只需要考虑3个问题：

1、路径：以及选择的路径

2、选择列表：可以选择的路径

3、结束条件：到达决策树底部，无法在选择路径的条件

整个回溯法的框架：

 其核心是for循环中递归。

下面看看这道题具体怎么回溯，我们来套框架。

具体分析

先上回溯代码

vector phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector res;
    string temp;
    void fun(string digits,int pos){
        if(pos == (digits.size() )){
            res.push_back(temp);
        }else{
            for(auto& i : phone[digits[pos] - '0']){
                temp += i;
                fun(digits,pos+1);
                temp.pop_back();
            }
        }
    }

其中phone相当于散列表，用于路径选择。 

1、本题路径就是电话号码digits，pos为当前选择第几位

2、结束条件为选择位置pos，已经指向digits末尾时结束，这时我们需要将路径放入res中

3、路径选择中，我们通过散列表phone可以得到一个字符串，这个字符串就是我们可以选择的路径。

下面是完整代码

---

代码

class Solution {
public:
    vector phone = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector res;
    string temp;
    void fun(string digits,int pos){
        if(pos == (digits.size() )){
            res.push_back(temp);
        }else{
            for(auto& i : phone[digits[pos] - '0']){
                temp += i;
                fun(digits,pos+1);
                temp.pop_back();
            }
        }
    }
    vector letterCombinations(string digits) {
        if((digits.size()) == 0){
            return res;
        }else{
            fun(digits,0);
        }
        return res;
    }
};