# 0017. 电话号码的字母组合

### 题目地址(17. 电话号码的字母组合)

<https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number>

### 题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

![image.png](https://p.ipic.vip/4xpxnc.jpg)

```

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

```

### 前置知识

* 回溯
* 笛卡尔积

### 公司

* 阿里
* 百度
* 字节
* 腾讯

### 回溯

#### 思路

由于要求所有的可能性，因此考虑使用回溯法进行求解。回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。

如果没有更多的数字需要被输入，说明当前的组合已经产生。

如果还有数字需要被输入：

* 遍历下一个数字所对应的所有映射的字母
* 将当前的字母添加到组合最后，也就是 str + tmp\[r]

#### 关键点

* 回溯
* 回溯模板

#### 代码

* 语言支持：JS, C++, Java, Python

JavaScript Code:

```js
/**
 * @param {string} digits
 * @return {string[]}
 */
const letterCombinations = function (digits) {
  if (!digits) {
    return [];
  }
  const len = digits.length;
  const map = new Map();
  map.set("2", "abc");
  map.set("3", "def");
  map.set("4", "ghi");
  map.set("5", "jkl");
  map.set("6", "mno");
  map.set("7", "pqrs");
  map.set("8", "tuv");
  map.set("9", "wxyz");
  const result = [];

  function generate(i, str) {
    if (i == len) {
      result.push(str);
      return;
    }
    const tmp = map.get(digits[i]);
    for (let r = 0; r < tmp.length; r++) {
      generate(i + 1, str + tmp[r]);
    }
  }
  generate(0, "");
  return result;
};
```

C++ Code:

```
class Solution {
public:
    string letterMap[10] = {" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res;
    vector<string> letterCombinations(string digits) {
        if(digits == "")
        {
            return res;
        }
        dfs(digits, 0, "");
        return res;
    }

    void dfs(string digits, int index, string s)
    {
        if(index == digits.length())
        {
            res.push_back(s);
            return;
        }
        // 获取当前数字
        char c = digits[index];
        // 获取数字对应字母
        string letters = letterMap[c-'0'];
        for(int i = 0 ; i < letters.length() ; i ++)
        {
            dfs(digits, index+1, s+letters[i]);
        }
    }
}
```

Java Code:

```java
class Solution {

    private String letterMap[] = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };
    private ArrayList<String> res;
    public List<String> letterCombinations(String digits) {
        res = new ArrayList<String>();
        if(digits.equals(""))
        {
            return res;
        }
        dfs(digits, 0, "");
        return res;
    }

    public void dfs(String digits, int index, String s)
    {
        if(index == digits.length())
        {
            res.add(s);
            return;
        }
        // 获取当前数字
        Character c = digits.charAt(index);
        // 获取数字对应字母
        String letters = letterMap[c-'0'];
        for(int i = 0 ; i < letters.length() ; i ++)
        {
            dfs(digits, index+1, s+letters.charAt(i));
        }
    }
}
```

Python Code:

```py
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        # 0-9
        self.d = [" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        self.res = []
        self.dfs(digits, 0, "")
        return self.res

    def dfs(self, digits, index, s):
        # 递归的终止条件,用index记录每次遍历到字符串的位置
        if index == len(digits):
            self.res.append(s)
            return
        # 获取当前数字
        c = digits[index]
        # print(c, int(c))
        # 获取数字对应字母
        letters = self.d[int(c)]
        # 遍历字符串
        for l in letters:
            # 调用下一层
            self.dfs(digits, index+1, s+l)
```

**复杂度分析**

N + M 是输入数字的总数

* 时间复杂度：O(2^N)，其中 N 为 digits 对于的所有可能的字母的和。
* 空间复杂度：O(2^N)，其中 N 为 digits 对于的所有可能的字母的和。

### 笛卡尔积

#### 思路

不难发现， 题目要求的是一个笛卡尔积。

比如 digits = 'ab'，其实就是 a 对应的集合 {'a', 'b', 'c'} 和 b 对应的集合 {'d', 'e', 'f'} 笛卡尔积。

简单回忆一下笛卡尔积的内容。对于两个集合 A 和 B，A×B = {(x,y)|x∈A∧y∈B}。

例如，A={a,b}, B={0,1,2}，则：

* A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}
* B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}

实际上，力扣关于笛卡尔积优化的题目并不少。 比如：

* [140. 单词拆分 II](https://github.com/azl397985856/fe-interview/issues/153)
* [95. 不同的二叉搜索树 II](/leetcode-solution/medium/95.unique-binary-search-trees-ii.md)
* 96.unique-binary-search-trees
* 等等

知道了这一点之后，就不难写出如下代码。

由于我们使用了笛卡尔积优化， 因此可以改造成纯函数，进而使用记忆化递归，进一步降低时间复杂度， 这是一个常见的优化技巧。

#### 关键点

* 笛卡尔积
* 记忆化递归

#### 代码

代码支持：Python3

```py

# 输入："23"
# 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        mapper = [" ", " ", "abc", "def", "ghi",
                  "jkl", "mno", "pqrs", "tuv", "wxyz"]
        @lru_cache(None)
        def backtrack(digits, start):
            if start >= len(digits):
                return ['']
            ans = []
            for i in range(start, len(digits)):
                for c in mapper[int(digits[i])]:
                    # 笛卡尔积
                    for p in backtrack(digits, i + 1):
                        # 需要过滤诸如  "d", "e", "f" 等长度不符合的数据
                        if start == 0:
                            if len(c + p) == len(digits):
                                ans.append(c + p)
                        else:
                            ans.append(c + p)
            return ans
        if not digits:
            return []
        return backtrack(digits, 0)

```

**复杂度分析**

N + M 是输入数字的总数

* 时间复杂度：O(N^2)，其中 N 为 digits 对于的所有可能的字母的和。
* 空间复杂度：O(N^2)，其中 N 为 digits 对于的所有可能的字母的和。

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/srtd7m.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/17.letter-combinations-of-a-phone-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.