17.电话号码的字母组合

题目描述

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

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解题思路

map<char, string> num2alpha = {
    {'2',"abc"},
    {'3',"def"},
    {'4',"ghi"},
    {'5',"jkl"},
    {'6',"mno"},
    {'7',"pqrs"},
    {'8',"tuv"},
    {'9',"wxyz"}
};

void LetterCombinationHelper(string& digits, int index, char* cur, vector<string>& ret){
    if(index == digits.length()){
        ret.push_back(string(cur));
        return;
    }
    
    for(auto c : num2alpha[digits[index]]){
        cur[index] = c;
        LetterCombinationHelper(digits, index+1, cur, ret);
    }
}
vector<string> LetterCombination(string digits){
    vector<string> ret;
    if(digits.length()<1){
        return ret;
    }
    
    char* cur = new char[digits.length()];
    LetterCombinationHelper(digits, 0, cur, ret);
    return ret;
}