0017. 电话号码的字母组合

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

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

题目描述

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

image.png

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

示例:

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

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

前置知识

• 回溯

• 笛卡尔积

公司

• 阿里

• 百度

• 字节

• 腾讯

回溯

思路

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

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

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

• 遍历下一个数字所对应的所有映射的字母

• 将当前的字母添加到组合最后，也就是 str + tmp[r]

关键点

• 回溯

• 回溯模板

代码

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

JavaScript Code:

/**
 * @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:

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:

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

• 95. 不同的二叉搜索树 II

• 96.unique-binary-search-trees

• 等等

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

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

关键点

• 笛卡尔积

• 记忆化递归

代码

代码支持：Python3

# 输入："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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。