Tuesday, November 18, 2014

[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.
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:backtracking

和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母,并加入当前combination中传到下一层递归。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> lettComb;
        string dict[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string comb(digits.size(),'\0');
        findLettComb(digits, 0, dict, comb, lettComb);
        return lettComb;
    }
    
    void findLettComb(string &digits, int index, string dict[], string &comb, vector<string> &lettComb) {
        if(index==digits.size()) {
            lettComb.push_back(comb);
            return;
        }
        
        string lett= dict[digits[index] - '0'];
        for(int i=0; i<lett.size(); i++) {
            comb[index] = lett[i];
            findLettComb(digits, index+1, dict, comb, lettComb);
        }
    }
};


方法2:插入法

当已经获得digits[0:i-1]的所有letter combinations以后,加入digits[i]后新combinations为加入每个可能对应的字母加到之前的解集中。这里需要克隆多份之前的解集。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> lettComb;
        lettComb.push_back("");
        string dict[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for(int i=0; i<digits.size(); i++) {
            int n = lettComb.size();
            string lett = dict[digits[i]-'0'];
            for(int j=0; j<n; j++) {
                for(int k=1; k<lett.size(); k++) {
                    string comb = lettComb[j];  //clone lettComb[j]
                    comb.push_back(lett[k]);
                    lettComb.push_back(comb);
                }
                lettComb[j].push_back(lett[0]);
            }
        }
        return lettComb;
    }
};

No comments:

Post a Comment