Description
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.
Example
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.
Discussion
这是一个典型的遍历搜索问题。我们可以采用深度优先搜索的方法。输入给出一串数字，每一个数字给搜索树加一层。
算法的时间复杂度为O(3^n)。
C++ Code
class Solution {
public:
vector<string> letterCombinations(string digits) {
string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> answer;
if(digits.length() == 0)
{
return answer;
}
dfs(digits, dict, 0, "", answer);
return answer;
}
void dfs(string digits, string dict[], int level, string prefix, vector<string> &answer)
{
if(level == digits.length())
{
answer.push_back(prefix);
return;
}
int index = digits[level] - '2'; //在字典dict中的下标
//遍历该数字对应的每一种字符情况
for(int i = 0; i < dict[index].size(); i++)
{
dfs(digits, dict, level + 1, prefix + dict[index][i], answer);
}
}
};