电话号码的字符组合（leetcode_17）
2020年2月11日
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
(就是键盘上九宫格那种)
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
我自己的的想法是建树，就是建立字典树，然后遍历字典树得到我们想要的字符串的排列组合。不过这种做法好像有点慢，就是只比70%的人快，这样好像不太行。
大佬的做法是建立个队列，每次遍历队列元素，在每个元素的末尾添加下一个字符可能的组合后依次加入队尾，然后将队首元素删除。由此反复最终得到我们想要的所有组合。
我的代码
class tree
{
public:
tree *value[26];
tree(char v) : current_value(v)
{
for (int i = 0; i < 26; ++i)
value[i] = NULL;
}
char current_value;
};
class Solution
{
public:
vector<string> letterCombinations(string digits)
{
if (digits.empty())
return vector<string>{};
string two = "abc";
string three = "def";
string four = "ghi";
string five = "jkl";
string six = "mno";
string seven = "pqrs";
string eight = "tuv";
string nine = "wxyz";
tree *root = new tree('*');
for (int i = 0; i < digits.size(); ++i)
{
switch (digits[i])
{
case '2':
build_tree(root, two, 0, i);
break;
case '3':
build_tree(root, three, 0, i);
break;
case '4':
build_tree(root, four, 0, i);
break;
case '5':
build_tree(root, five, 0, i);
break;
case '6':
build_tree(root, six, 0, i);
break;
case '7':
build_tree(root, seven, 0, i);
break;
case '8':
build_tree(root, eight, 0, i);
break;
case '9':
build_tree(root, nine, 0, i);
break;
}
}
tree_combination(root, "", digits.size(), 0);
for (auto &i : my_combinatioin)
{
i.erase(0, 1);
}
return my_combinatioin;
}
void build_tree(tree *root, string character, int current_depth, int required_depth)
{
if (required_depth == current_depth)
{
for (int i = 0; i < character.size(); ++i)
{
root->value[character[i] - 'a'] = new tree(character[i]);
}
}
else
{
for (int i = 0; i < 26; ++i)
{
if (root->value[i] != NULL)
build_tree(root->value[i], character, current_depth + 1, required_depth);
}
}
}
void tree_combination(tree *root, string combination, int required_depth, int current_depth)
{
char current_character = root->current_value;
combination.push_back(current_character);
if (required_depth == current_depth)
{
my_combinatioin.push_back(combination);
}
for (int i = 0; i < 26; ++i)
{
if (root->value[i] != NULL)
{
tree_combination(root->value[i], combination, required_depth, current_depth + 1);
}
}
}
vector<string> my_combinatioin;
};
大佬的代码
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
string temp;
queue<string> que;
string chars = getChars(digits[0]);
for (auto& c : chars) {
temp = c;
que.push(temp);
}
for(int i = 1; i < digits.size(); i++){
chars = getChars(digits[i]);
for (int removedSize = que.size(); removedSize > 0; removedSize--) {
for (auto& c : chars) {
temp = que.front();
que.push(temp + c);
}
que.pop();
}
}
int size = que.size();
for(int i = 0; i < size; i++){
temp = que.front();
que.pop();
res.push_back(temp);
}
return res;
}
string getChars(char digit) {
string chars;
switch (digit) {
case '2':
chars = "abc";
break;
case '3':
chars = "def";
break;
case '4':
chars = "ghi";
break;
case '5':
chars = "jkl";
break;
case '6':
chars = "mno";
break;
case '7':
chars = "pqrs";
break;
case '8':
chars = "tuv";
break;
case '9':
chars = "wxyz";
break;
}
return chars;
}
};
Previous
最长回文子串（leetcode_5）
Newer