leetcode刷题：17.电话号码的字母组合

leetcode原题网页

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

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

思路：使用vector，进行深度优先遍历

每个按键所对应的字母都是固定的。可以先创建一个数字到字母的映射数组。

vector<string>NumStrArr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

对于每一个可能得到的输入数字序列，由于每一个数字可能对应多个字母，当多个数字组合输入时，则会出现树形组合方式，如下图：

采用深度优先遍历的方法，即每次操作遍历完树的层数。结束一次遍历以后进行回溯，回溯到上一层再取上一层的下一个字母往下递归，直至上一层字母全部取完。

其实就是不断寻找所有可行解的过程，但是对于本题来说，每个字母组合都是可行的解。

class Solution {
    vector<string>NumStrArr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    void Combine(const string& digits,int i,const string& combinestr, vector<string>& v)
    {
        //i为目前所操作的数字在dights中的下标

        if(i == digits.size())        //遍历层数已达最大，已找到一个序列组合，执行插入和回退操作
        {
            v.push_back(combinestr);
            return;
        }
        int n=digits[i]-'0';
        string str=NumStrArr[n];
        for(auto ch:str)              //对于当前层数字所对应的string进行遍历
        {
            Combine(digits, i+1, combinestr+ch, v);
        }
    }
    vector<string> letterCombinations(const string& digits) {
       vector<string> v;
       if(digits.empty())    //如果digits为空表示没有输入，直接返回
            return v;
        string str;          //str用于维护可能的的字母组合
        Combine(digits, 0, str, v);
        return v;
    }
};