LeetCode_17: Letter Combinations of a Phone Number - LeetCode

# 引言

题目链接：https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

题目给出的图和九键拼音输入法类似，2 对应的是 abc,3 对应的 def, 这样。现在给出一个数字序列，要求输出这个数字序列可以打出的所有字符串组合。

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

基础的搜索题目，直接常规 bfs 或者 dfs 即可

时间复杂度 O(4^n) , 4 表示每个数字最多可以映射的字符个数

空间复杂度 O(4^n)

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
	}