[Leetcode] Letter Combinations of a Phone Number-蒲公英云

[Leetcode] Letter Combinations of a Phone Number

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.

200px-Telephone-keypad2.svg.png

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

模拟！

1 class Solution {
 2 public:
 3     string key[10];
 4     void initKey() {
 5         key[0] = " ";
 6         key[1] = "";
 7         key[2] = "abc";
 8         key[3] = "def";
 9         key[4] = "ghi";
10         key[5] = "jkl";
11         key[6] = "mno";
12         key[7] = "pqrs";
13         key[8] = "tuv";
14         key[9] = "wxyz";
15     }
16     void findNext(vector<string> &res, string &digits, string s, int idx) {
17         if (s.length() == digits.length()) {
18             res.push_back(s);
19             return;
20         }
21         int k = digits[idx] - '0';
22         for (int i = 0; i < key[k].length(); ++i) {
23             findNext(res, digits, s + key[k][i], idx + 1);
24         }
25     }
26     vector<string> letterCombinations(string digits) {
27         initKey();
28         vector<string> res;
29         string s;
30         findNext(res, digits, s, 0);
31         return res;
32     }
33 };