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.

思路

我们可以利用回溯的方法来解决这道题。

我们不需要改变原有数组，利用标志位‘pos’来标定访问到了哪一层即可。如果采用添加删除的操作，会比较耗时。注意，如果需要跳出回溯，在相应的部分要加入return语句。

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 {
private:
    const string telephone[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> result;
public:
    void letterBackTrack(string digits, string cur, string res, int pos) {
        pos++;
        if(pos != digits.size()){
            string new_cur = telephone[digits[pos] - '0'];
            for(int i = 0; i < cur.size(); i++){
                string new_res = res;
                new_res.push_back(cur[i]);
                letterBackTrack(digits, new_cur, new_res, pos);
            }
        }
        else{
            for(int i = 0; i < cur.size(); i++){
                string new_res = res;
                new_res.push_back(cur[i]);
                result.push_back(new_res);
            }
            return;
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() != 0)
            letterBackTrack(digits, telephone[digits.front()-'0'], "", 0);
        return result;
    }
};