【LeetCode回溯算法#03】电话号码的字母组合（数字映射字母）

电话号码的字母组合

力扣题目链接(opens new window)

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

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

示例:

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

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

思路

题目给的例子好像可以用for循环解决，但是输入一旦变多，就又碍于for循环的深度限制而无法解决了

所以还是得用回溯

本题与 组合问题 很像，我们要解决的问题如下：

• 数字和字母之间如何映射？
• 用回溯解决for循环深度不足的问题，从而遍历出所有组合结果

数字和字母如何映射

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

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

代码分析

1、确定回溯函数的参数与返回值

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

输入参数是题目给的digits，另外还需要一个参数index，用来指明当前遍历到了digits中的哪个数（index也表示树的深度）

class Solution {
    //定义一个map用来映射数组与字母
private:
    string letterMap[10] = {
        ...
    };
    //确定回溯函数的参数和返回值
    vector<string> res;
    string saveStr;//用于保存叶子结点出的字符串
    void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数        
    }
public:
    vector<string> letterCombinations(string digits) {      
    }
};

2、确定终止条件

index等于输入数字个数就结束，相当于遍历完一遍digits

class Solution {
    //定义一个map用来映射数组与字母
private:
    string letterMap[10] = {
        ...
    };
    //确定回溯函数的参数和返回值
    vector<string> res;
    string saveStr;//用于保存叶子结点出的字符串
    void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数
        //确定终止条件
        if(index == digits.size()){//index等于输入数字个数就结束，即遍历完一遍digits
            res.push_back(saveStr);
            return;
        }        
    }
public:
    vector<string> letterCombinations(string digits) {
    }
};

3、确定单层处理逻辑

首先要取index指向的数字，即从输入数字字符串取数字并转为整型

然后从映射表中取出对应数字的字母映射

class Solution {
    //定义一个map用来映射数组与字母
private:
    string letterMap[10] = {
        "",     //0
        "",     //1
        "abc",  //2
        "def",  //3
        "ghi",  //4
        "jkl",  //5
        "mno",  //6
        "pqrs", //7
        "tuv",  //8
        "wxyz"  //9
    };
    //确定回溯函数的参数和返回值
    vector<string> res;
    string saveStr;//用于保存叶子结点出的字符串
    void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数
        //确定终止条件
        if(index == digits.size()){//index等于输入数字个数就结束，即遍历完一遍digits
            res.push_back(saveStr);
            return;
        }
        //确定单层处理逻辑
        //从输入数字字符串取数字并转为整型
        int singleDigi = digits[index] - '0';
        //从映射表中取出对应数字的字母映射
        string digiMap = letterMap[singleDigi];
        for(int i = 0; i < digiMap.size(); ++i){
            saveStr.push_back(digiMap[i]);
            backtracking(digits, index + 1);
            saveStr.pop_back();//回溯处理
        }
    }
public:
    vector<string> letterCombinations(string digits) {
    }
};

注意这里for循环是从0开始遍历，因为手机按键是从0~9

代码

class Solution {
    //定义一个map用来映射数组与字母
private:
    string letterMap[10] = {
        "",     //0
        "",     //1
        "abc",  //2
        "def",  //3
        "ghi",  //4
        "jkl",  //5
        "mno",  //6
        "pqrs", //7
        "tuv",  //8
        "wxyz"  //9
    };
    //确定回溯函数的参数和返回值
    vector<string> res;
    string saveStr;//用于保存叶子结点出的字符串
    void backtracking(string& digits, int index){//index是用来指明当前遍历到了digits中的哪个数
        //确定终止条件
        if(index == digits.size()){//index等于输入数字个数就结束，即遍历完一遍digits
            res.push_back(saveStr);
            return;
        }
        //确定单层处理逻辑
        //从输入数字字符串取数字并转为整型
        int singleDigi = digits[index] - '0';
        //从映射表中取出对应数字的字母映射
        string digiMap = letterMap[singleDigi];
        for(int i = 0; i < digiMap.size(); ++i){
            saveStr.push_back(digiMap[i]);
            backtracking(digits, index + 1);
            saveStr.pop_back();//回溯处理
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if(digits == "") return res;
        backtracking(digits, 0);
        return res;
    }
};

注意点

1、数字字符串转为整型的操作

2、TBD