17. Letter Combinations of a Phone Number**
17. Letter Combinations of a Phone Number**
作者：珍妮的选择
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
题目描述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.
C++ 实现 1DFS + Backtracing. 注意对 digits 为空的处理.
class Solution {
private:
unordered_map<char, vector> phone = {
{'2', {"a", "b", "c"}},
{'3', {"d", "e", "f"}},
{'4', {"g", "h", "i"}},
{'5', {"j", "k", "l"}},
{'6', {"m", "n", "o"}},
{'7', {"p", "q", "r", "s"}},
{'8', {"t", "u", "v"}},
{'9', {"w", "x", "y", "z"}}
};
void combine(const string &digits, int k, string &cur, vector &res) {
if (k >= digits.size()) {
res.push_back(cur);
return;
}
for (auto &s : phone[digits[k]]) {
cur += s;
combine(digits, k + 1, cur, res);
cur.pop_back();
}
}
public:
vector letterCombinations(string digits) {
if (digits.empty()) return {};
vector res;
string cur;
combine(digits, 0, cur, res);
return res;
}
};
作者：珍妮的选择
