电话号码的字母组合

问题描述

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

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

思路

首先在电话号码的数字和字母之间进行一个映射， map<char, string> table;
vector ret作为最后返回的结果，cur作为中间暂存结果，当递归次数index等于digits.length()时，将cur存入到ret中
当index小于digits.length()时，

for(int i=0;i<table[digits[index]].length();i++){
            dfs(digits,cur + table[digits[index]][i],index + 1);
        }

题解

class Solution {
public:
    map<char, string> table;

    void init() {
        table['2'] = "abc";
        table['3'] = "def";
        table['4'] = "ghi";
        table['5'] = "jkl";
        table['6'] = "mno";
        table['7'] = "pqrs";
        table['8'] = "tuv";
        table['9'] = "wxyz";
    }

    int len;
    vector<string> ret;

    vector<string> letterCombinations(const string &digits) {
        init();
        len = digits.length();
        if(len==0) return ret;
        dfs(digits, "",0);
        return ret;
    }

    void dfs(string digits, const string &cur,int index) {
        if (index == len) {
            ret.push_back(cur);
            return;
        }
        for(int i=0;i<table[digits[index]].length();i++){
            dfs(digits,cur + table[digits[index]][i],index + 1);
        }

    }
};