作者
Ivan Chien
始于
分类：LeetCode
Tags: [ LeetCode ]
LeetCode 百题计划 - 17. Letter Combinations of a Phone Number
始于
分类：LeetCode
Tags: [ LeetCode ]
LeetCode 百题计划 - 17. Letter Combinations of a Phone Number
LeetCode 17. Letter Combinations of a Phone Number
17. Letter Combinations of a Phone Number
Difficulty: medium
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
Input: “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.
一看就知道是dfs, 不多说, 上代码:
1st Version:
class Solution {
public:
vector<string> lst;
string* ds;
vector<string> letterCombinations(string digits) {
if (digits.empty())
return vector<string>();
ds = &digits;
dfs("", 0);
return this->lst;
}
void dfs(string prefix, int pos) {
if (pos >= ds->size()) {
this->lst.push_back(move(prefix));
return ;
}
switch((*ds)[pos] - '0') {
case 2:
dfs(prefix + "a", pos + 1);
dfs(prefix + "b", pos + 1);
dfs(prefix + "c", pos + 1);
break;
case 3:
dfs(prefix + "d", pos + 1);
dfs(prefix + "e", pos + 1);
dfs(prefix + "f", pos + 1);
break;
case 4:
dfs(prefix + "g", pos + 1);
dfs(prefix + "h", pos + 1);
dfs(prefix + "i", pos + 1);
break;
case 5:
dfs(prefix + "j", pos + 1);
dfs(prefix + "k", pos + 1);
dfs(prefix + "l", pos + 1);
break;
case 6:
dfs(prefix + "m", pos + 1);
dfs(prefix + "n", pos + 1);
dfs(prefix + "o", pos + 1);
break;
case 7:
dfs(prefix + "p", pos + 1);
dfs(prefix + "q", pos + 1);
dfs(prefix + "r", pos + 1);
dfs(prefix + "s", pos + 1);
break;
case 8:
dfs(prefix + "t", pos + 1);
dfs(prefix + "u", pos + 1);
dfs(prefix + "v", pos + 1);
break;
case 9:
dfs(prefix + "w", pos + 1);
dfs(prefix + "x", pos + 1);
dfs(prefix + "y", pos + 1);
dfs(prefix + "z", pos + 1);
break;
default:
break;
}
}
};
Rate:
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 9.4 MB, less than 5.71% of C++ online submissions for Letter Combinations of a Phone Number.
真的非常的快, 但是看到9.4MB的内存, 就知道这题没那么简单了.
看了一下讨论区好像内存用的也挺多的, 看了一下讨论区双百的代码, 感觉没什么太大区别, 搞不太懂. 总之代码贴上.
2nd Version:
// https://leetcode.com/problems/letter-combinations-of-a-phone-number/discuss/360946/C%2B%2B%3A-faster-100-in-time-and-100-in-memory
class Solution {
public:
vector<char> buff;
const map<char, string> mp = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"},
};
vector<string> letterCombinations(string digits) {
vector<string> solutions;
if(digits.empty()) {
return solutions;
}
buff = vector<char>(digits.size());
f(0, digits, solutions);
return solutions;
}
inline void f(const int &i, const string &str, vector<string> &solutions) {
if(i == (int) str.size()) {
solutions.push_back(string(buff.begin(), buff.end()));
return;
}
const char d = str[i];
for(const auto &c : mp.at(d)) {
buff[i] = c;
f(i + 1, str, solutions);
}
}
};
26个字母每个都写了一遍也是够白痴的..
其实中间我还写了一个版本, 但是效果不佳:
1.5th Version:
class Solution {
public:
vector<string> lst;
string* ds;
vector<string> letterCombinations(string digits) {
if (digits.empty())
return vector<string>();
ds = &digits;
string tmp = "";
dfs(tmp, 0);
return this->lst;
}
void dfs(string& prefix, int pos) {
if (pos >= ds->size()) {
this->lst.push_back(prefix);
} else {
switch((*ds)[pos] - '0') {
case 2:
prefix.push_back('a'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('b'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('c'); dfs(prefix, pos + 1); prefix.pop_back();
break;
case 3:
prefix.push_back('d'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('e'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('f'); dfs(prefix, pos + 1); prefix.pop_back();
break;
case 4:
prefix.push_back('g'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('h'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('i'); dfs(prefix, pos + 1); prefix.pop_back();
break;
case 5:
prefix.push_back('j'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('k'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('l'); dfs(prefix, pos + 1); prefix.pop_back();
break;
case 6:
prefix.push_back('m'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('n'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('o'); dfs(prefix, pos + 1); prefix.pop_back();
break;
case 7:
prefix.push_back('p'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('q'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('r'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('s'); dfs(prefix, pos + 1); prefix.pop_back();
break;
case 8:
prefix.push_back('t'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('u'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('v'); dfs(prefix, pos + 1); prefix.pop_back();
break;
case 9:
prefix.push_back('w'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('x'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('y'); dfs(prefix, pos + 1); prefix.pop_back();
prefix.push_back('z'); dfs(prefix, pos + 1); prefix.pop_back();
break;
default:
assert(false);
break;
}
}
}
};