题目

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

思路

排列组合的递归方法

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len = digits.length();
        vector<string> result;
        string str = "";  
        myLettercomb(result, str, digits, 0);
        return result;
    }
    
    void myLettercomb(vector<string> &result, string & str, string &digits, int cur) {
        const static string key_maps[10]={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        if(cur==digits.length()) {
            result.push_back(str);
            return ;
        }
        int num = digits[cur]-'0';
        for(int i=0; i<key_maps[num].length(); i++) {
            str = str+key_maps[num][i];
            myLettercomb(result, str, digits, cur+1);
            str.erase(str.length()-1);
        }        
    }        
};