Skip to content

Latest commit

 

History

History
296 lines (219 loc) · 10.5 KB

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

File metadata and controls

296 lines (219 loc) · 10.5 KB

欢迎大家参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

17.电话号码的字母组合

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

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

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

17.电话号码的字母组合

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

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

思路

从示例上来说,输入"23",最直接的想法就是两层for循环遍历了吧,正好把组合的情况都输出了。

如果输入"233"呢,那么就三层for循环,如果"2333"呢,就四层for循环.......

大家应该感觉出和回溯算法:求组合问题!遇到的一样的问题,就是这for循环的层数如何写出来,此时又是回溯法登场的时候了。

理解本题后,要解决如下三个问题:

  1. 数字和字母如何映射
  2. 两个字母就两个for循环,三个字符我就三个for循环,以此类推,然后发现代码根本写不出来
  3. 输入1 * #按键等等异常情况

数字和字母如何映射

可以使用map或者定义一个二位数组,例如:string letterMap[10],来做映射,我这里定义一个二维数组,代码如下:

const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
};

回溯法来解决n个for循环的问题

对于回溯法还不了解的同学看这篇:关于回溯算法,你该了解这些!

例如:输入:"23",抽象为树形结构,如图所示:

17. 电话号码的字母组合

图中可以看出遍历的深度,就是输入"23"的长度,而叶子节点就是我们要收集的结果,输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

回溯三部曲:

  • 确定回溯函数参数

首先需要一个字符串s来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量我依然定义为全局。

再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index。

注意这个index可不是 回溯算法:求组合问题!回溯算法:求组合总和!中的startIndex了。

这个index是记录遍历第几个数字了,就是用来遍历digits的(题目中给出数字字符串),同时index也表示树的深度。

代码如下:

vector<string> result;
string s;
void backtracking(const string& digits, int index)
  • 确定终止条件

例如输入用例"23",两个数字,那么根节点往下递归两层就可以了,叶子节点就是要收集的结果集。

那么终止条件就是如果index 等于 输入的数字个数(digits.size)了(本来index就是用来遍历digits的)。

然后收集结果,结束本层递归。

代码如下:

if (index == digits.size()) {
    result.push_back(s);
    return;
}
  • 确定单层遍历逻辑

首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。

然后for循环来处理这个字符集,代码如下:

int digit = digits[index] - '0';        // 将index指向的数字转为int
string letters = letterMap[digit];      // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
    s.push_back(letters[i]);            // 处理
    backtracking(digits, index + 1);    // 递归,注意index+1,一下层要处理下一个数字了
    s.pop_back();                       // 回溯
}

注意这里for循环,可不像是在回溯算法:求组合问题!回溯算法:求组合总和!中从startIndex开始遍历的

因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合,而77. 组合216.组合总和III都是是求同一个集合中的组合!

注意:输入1 * #按键等等异常情况

代码中最好考虑这些异常情况,但题目的测试数据中应该没有异常情况的数据,所以我就没有加了。

但是要知道会有这些异常,如果是现场面试中,一定要考虑到!

C++代码

关键地方都讲完了,按照关于回溯算法,你该了解这些!中的回溯法模板,不难写出如下C++代码:

// 版本一
class Solution {
private:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    vector<string> result;
    string s;
    void backtracking(const string& digits, int index) {
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';        // 将index指向的数字转为int
        string letters = letterMap[digit];      // 取数字对应的字符集
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);            // 处理
            backtracking(digits, index + 1);    // 递归,注意index+1,一下层要处理下一个数字了
            s.pop_back();                       // 回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

一些写法,是把回溯的过程放在递归函数里了,例如如下代码,我可以写成这样:(注意注释中不一样的地方)

// 版本二
class Solution {
private:
        const string letterMap[10] = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
        };
public:
    vector<string> result;
    void getCombinations(const string& digits, int index, const string& s) { // 注意参数的不同
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); i++) {
            getCombinations(digits, index + 1, s + letters[i]);  // 注意这里的不同
        }
    }
    vector<string> letterCombinations(string digits) {
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        getCombinations(digits, 0, "");
        return result;

    }
};

我不建议把回溯藏在递归的参数里这种写法,很不直观,我在二叉树:以为使用了递归,其实还隐藏着回溯这篇文章中也深度分析了,回溯隐藏在了哪里。

所以大家可以按照版本一来写就可以了。

总结

本篇将题目的三个要点一一列出,并重点强调了和前面讲解过的77. 组合216.组合总和III的区别,本题是多个集合求组合,所以在回溯的搜索过程中,都有一些细节需要注意的。

其实本题不算难,但也处处是细节,大家还要自己亲自动手写一写。

其他语言版本

Java:

class Solution {

    //设置全局列表存储最后的结果
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
        //初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串""
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //迭代处理
        backTracking(digits, numString, 0);
        return list;

    }

    //每次迭代获取一个字符串,所以会设计大量的字符串拼接,所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0,则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
        //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            //回溯
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

Python:

Go: