LeetCode_17: Letter Combinations of a Phone Number

# 引言

题目链接：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
}