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

class Solution { public: vector<string> letterCombinations(string digits) { vector<string>ans; dfs(digits,0,"",ans); return ans; } void dfs(string digits, int start, string s, vector<string>&ans){ if(start == digits.size()){ if(s != "") ans.push_back(s); return; } int cnt = digits[start]-'2'; for(int i = 0; i < 4; i++) if(letter[cnt][i] != '!') dfs(digits, start+1,s+letter[cnt][i],ans); } char letter[8][4] = { {'a', 'b', 'c', '!'}, {'d', 'e', 'f', '!'}, {'g', 'h', 'i', '!'}, {'j', 'k', 'l', '!'}, {'m', 'n', 'o', '!'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v', '!'}, {'w', 'x', 'y', 'z'} }; };