LeetCode: "Letter Combinations of a Phone Number

一些小问题， “”的输出我的是[], 但是答案却是[""]，比较难理解，3次过

 1 class Solution {
 2 public:
 3     void dfs(vector<string> &ret, string tmp, map<char, string> refer, string digits, int beg) {
 4         if (beg >= digits.size()) {
 5             ret.push_back(tmp);
 6             return;
 7         }
 8         if (digits[beg] <= '9' && digits[beg] >= '2') {
 9             for (int i = 0; i < refer[digits[beg]].size(); i++) {
10                 string r = refer[digits[beg]];
11                 dfs(ret, tmp+r[i], refer, digits, beg+1);
12             }
13         }
14     }
15     vector<string> letterCombinations(string digits) {
16         // Start typing your C/C++ solution below
17         // DO NOT write int main() function
18         map<char, string> refer;
19         refer['2'] = "abc";
20         refer['3'] = "def";
21         refer['4'] = "ghi";
22         refer['5'] = "jkl";
23         refer['6'] = "mno";
24         refer['7'] = "pqrs";
25         refer['8'] = "tuv";
26         refer['9'] = "wxyz";
27         vector<string> ret;
28         string tmp = "";
29         dfs(ret, tmp, refer, digits, 0);
30         return ret;
31     }
32 };

加一个iterative的方法

 1 class Solution {
 2 public:
 3     vector<string> letterCombinations(string digits) {
 4         // IMPORTANT: Please reset any member data you declared, as
 5         // the same Solution instance will be reused for each test case.
 6         map<char, string> S;
 7         S['2'] = "abc", S['3'] = "def", S['4'] = "ghi", S['5'] = "jkl";
 8         S['6'] = "mno", S['7'] = "pqrs", S['8'] = "tuv", S['9'] = "wxyz";
 9         queue<string> que;
10         vector<string> res;
11         if (digits.size() == 0) {
12             res.push_back("");
13             return res;
14         }
15         for (int i = 0; i < S[digits[0]].size(); i++) que.push(string("")+S[digits[0]][i]);
16         while (!que.empty()) {
17             string tmp = que.front();
18             que.pop();
19             if (tmp.size() == digits.size()) res.push_back(tmp);
20             else for (int i = 0; i < S[digits[tmp.size()]].size(); i++) que.push(tmp+S[digits[tmp.size()]][i]);
21         }
22         return res;
23     }
24 };

 1 public class Solution {
 2     public List<string> LetterCombinations(string digits) {
 3         Dictionary<char, string> S = new Dictionary<char, string>();
 4         S.Add('2', "abc"); S.Add('3', "def"); S.Add('4', "ghi"); S.Add('5', "jkl");
 5         S.Add('6', "mno"); S.Add('7', "pqrs"); S.Add('8', "tuv"); S.Add('9', "wxyz");
 6         Queue<string> que = new Queue<string>();
 7         List<string> ans = new List<string>();
 8         if (digits.Length == 0) return ans;
 9         foreach (var s in S[digits[0]]) que.Enqueue("" + (char)s);
10         while (que.Count != 0) {
11             string peek = que.Peek();
12             que.Dequeue();
13             if (peek.Length == digits.Length) ans.Add(peek);
14             else foreach(var s in S[digits[peek.Length]]) que.Enqueue(peek + (char)s);
15         }
16         return ans;
17     }
18 }

View Code