1. 首页

LeetCode 017. 电话号码的字母组合

题目描述

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

image.png


给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

难度:Middle

前置知识

  • 回溯
  • 笛卡尔积

公司

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

回溯

思路

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

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

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

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

关键点

  • 回溯
  • 回溯模板

代码

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

JavaScript Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.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:

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)}

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

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

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

关键点

  • 笛卡尔积
  • 记忆化递归

Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js……等,以帮助开发者成长为愿景的社区

代码

代码支持: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链接:17.Letter-Combinations-of-a-Phone-Number

更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 017. 电话号码的字母组合

链接:https://www.javascriptc.com/4377.html

« LeetCode 018. 四数之和
LeetCode 016. 最接近的三数之和»
Flutter 中文教程资源

相关推荐

QR code