# 引言
题目链接:https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
# 题目大意
题目给出的图和九键拼音输入法类似,2 对应的是 abc,3 对应的 def, 这样。现在给出一个数字序列,要求输出这个数字序列可以打出的所有字符串组合。
- Example
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
# 题解
# 一句话题解
基础的搜索题目,直接常规 bfs 或者 dfs 即可
# 复杂度
时间复杂度 O(4^n)
, 4 表示每个数字最多可以映射的字符个数
空间复杂度 O(4^n)
# AC 代码
c++
bfs 版本
// bfs | |
class Solution | |
{ | |
public: | |
vector<string> letterCombinations(string digits) | |
{ | |
if (digits.length() <= 0) | |
{ | |
return {}; | |
} | |
unordered_map<int, string> keyHash{ | |
{0, " "}, | |
{1, ""}, | |
{2, "abc"}, | |
{3, "def"}, | |
{4, "ghi"}, | |
{5, "jkl"}, | |
{6, "mno"}, | |
{7, "pqrs"}, | |
{8, "tuv"}, | |
{9, "wxyz"}}; | |
vector<string> ans{""}; | |
for (const char digit : digits) | |
{ | |
vector<string> tmp; | |
for (const char c : keyHash[digit - '0']) | |
{ | |
for (string str : ans) | |
{ | |
tmp.push_back(str + c); | |
} | |
} | |
swap(ans, tmp); | |
} | |
return ans; | |
} | |
}; |
c++
dfs 版本
// dfs | |
class Solution | |
{ | |
public: | |
vector<string> letterCombinations(string digits) | |
{ | |
if (digits.length() <= 0) | |
{ | |
return {}; | |
} | |
unordered_map<int, string> keyHash{ | |
{0, " "}, | |
{1, ""}, | |
{2, "abc"}, | |
{3, "def"}, | |
{4, "ghi"}, | |
{5, "jkl"}, | |
{6, "mno"}, | |
{7, "pqrs"}, | |
{8, "tuv"}, | |
{9, "wxyz"}}; | |
vector<string> ans; | |
string cur; | |
dfs(cur, 0, ans, digits, keyHash); | |
return ans; | |
} | |
private: | |
void dfs(string &cur, int index, vector<string> &ans, | |
string &digits, unordered_map<int, string> &keyHash) | |
{ | |
if (index == digits.length()) | |
{ | |
ans.push_back(cur); | |
return; | |
} | |
string curStr = keyHash[digits[index] - '0']; | |
for (char c : curStr) | |
{ | |
cur.push_back(c); | |
dfs(cur, index + 1, ans, digits, keyHash); | |
cur.pop_back(); | |
} | |
} | |
}; |
go
版本
// bfs | |
func letterCombinations(digits string) []string { | |
if len(digits) <= 0 { | |
return nil | |
} | |
keyHash := map[int]string{0: " ", 1: "", 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"} | |
ans := []string{""} | |
for _, digit := range digits { | |
var tmp []string | |
for _, c := range keyHash[int(digit-'0')] { | |
for _, str := range ans { | |
tmp = append(tmp, str+string(c)) | |
} | |
} | |
ans, tmp = tmp, ans | |
} | |
return ans | |
} |