LeetCode 0017 - Letter Combinations of a Phone Number
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a string containing digits from 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 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遍历答案即可,时间复杂度为 ,其中 为 的出现次数, 为 的出现次数。
细节问题:
- 注意特判空串。
# AC代码
class Solution {
public:
vector<string> letterCombinations(string digits) {
// 特判
if (digits.length() == 0) {
return vector<string>();
}
// DFS
vector<string> res;
string str = "";
dfs(0, str, res, digits);
// 返回
return res;
}
// 深度优先搜索
void dfs(int depth, string & str, vector<string> & res, const string & digits) {
// 递归终止
if (depth == digits.length()) {
res.push_back(str);
return;
}
// 递归
const string & lst = mp[digits[depth] - '2'];
for (int i = 0; i < lst.length(); i ++) {
str += lst[i];
dfs(depth + 1, str, res, digits);
str.pop_back();
}
}
// 常量
const vector<string> mp = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01