17. Letter Combinations of a Phone Number

python

class Solution:
    def letterCombinations(self, digits):
        # dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        # 
        # result = [''] if len(digits) > 0 else []
        # for i in digits:
        #     temp_comb = []
        #     for r in result:
        #         for d in dict[i]:
        #             temp_comb.append(r+d)
        #     result = temp_comb
        # 
        # return result
        dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl','6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}

        if len(digits) == 0:
            return []
        if len(digits) == 1:
            return list(dict[digits[0]])

        rear = dict[digits[-1]]
        front = self.letterCombinations(digits[:-1])
        return [f+r for f in front for r in rear]
        
        

c++

vector<string> letterCombinations(string digits) {
    vector<string> result;
    if(digits.empty()) return vector<string>();
    static const vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    result.push_back("");   // add a seed for the initial case
    for(int i = 0 ; i < digits.size(); ++i) {
        int num = digits[i]-'0';
        if(num < 0 || num > 9) break;
        const string& candidate = v[num];
        if(candidate.empty()) continue;
        vector<string> tmp;
        for(int j = 0 ; j < candidate.size() ; ++j) {
            for(int k = 0 ; k < result.size() ; ++k) {
                tmp.push_back(result[k] + candidate[j]);
            }
        }
        result.swap(tmp);
    }
    return result;
}