# 17 - Letter Combinations of a Phone Number

解法一 - Backtracking

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> sol;
        if(digits.length() < 1) return sol;
        string state = "";

        unordered_map<char, vector<char>> table;
        table['2'] = {'a','b','c'};
        table['3'] = {'d','e','f'};
        table['4'] = {'g','h','i'};
        table['5'] = {'j','k','l'};
        table['6'] = {'m','n','o'};
        table['7'] = {'p','q','r','s'};
        table['8'] = {'t','u','v'};
        table['9'] = {'w','x','y','z'};

        helper(digits, sol, state, table);

        return sol;
    }

private:
    void helper(string digits, vector<string>& sol, string& state, unordered_map<char, vector<char>>& table) {
        if(digits == "") {
            sol.push_back(state);
            return;
        }
        else {
            char c = digits[0];
            for(int i=0; i<table[c].size(); i++) {
                state.push_back(table[c][i]);
                digits = digits.substr(1,string::npos);
                helper(digits, sol, state, table);
                digits.insert(0,1,c);
                state.pop_back();
            }
        }
    }
};

// idea: need a mapping from digit to char
// when go to one number, replace that number with all possible chars and do dfs again