题目

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.

img

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

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

大意

像图中一样，给定一个数字字符串，输出所有可能的英文字符串。

答案1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        int len =digits.size();
        vector<string> res;
        if(len==0) return res;
        res.push_back("");
        string s[10] ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
      	//先声明一个string 类型的数组。
        for(int i=0; i<len; i++)
        {
            vector<string> temps;
            string chars = s[digits[i]-'0'];
          	//chars是当前数字对应的字符串。
            for(int c=0;c<chars.size();c++)
            {	//chars中每个字符进行遍历。
                for(int j=0;j<res.size();j++)
                  // res里是前面已经存进去的所有字符串，现在要和chars中的每个字符进行交叉组合。
                    temps.push_back(res[j]+chars[c]);
            }
          	// 组合完成后，把新的res(temps)赋值给老的res.
            res =temps;
        }
        return res;
    }
};

迭代的思想，数字字符串每多一个字符，就是把前面已经存进去的所有字符串和这个新增加数字字符串进行穷举组合。得到最终的res.

答案2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<string> res;
    vector<string> letterCombinations(string digits) {
        int len =digits.size();
        if(len==0) return res;
        // res.push_back("");
        string ss = "";
        string s[10] ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        DFS(0,digits,ss, s);
        return res;
    }
  	//index 记录digits到第几位，ss是DFS中拼装的字符串，s[10]是定义的String数组。
    void DFS(int index, string digits, string ss ,string s[10])
    {
        if(index==digits.size())
        {
            res.push_back(ss);
        }
        else
        {
            for(int i = 0; i < s[digits[index] - '0'].size(); i++)
           {
              //DFS中ss+s[digits[index] - '0'][i] 加号后面的部分就相当于push_back().
                DFS(index + 1, digits, ss+s[digits[index] - '0'][i], s);
              //这里，DFS中ss+s[digits[index] - '0'][i]不同的i值实际隐藏了pop_back的动作。
           }
        }      
    }
};

深度优先遍历，字符串的深度优先遍历更为简单，不用像vector一样push_back pop_back，可以直接在string后面加上某个字符，就相当于push_back了，下一次直接加上不同的字符就好。

思路

两种方法，可以迭代，可以递归。

一般这种需要遍历所有情况的问题一看就是要用DFS进行遍历。