问题描述

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以任何顺序返回。给定数字到字母的映射如下(与电话按键相同),1不对应任何字母。

输入输出样例

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

"2"对应的字符串是abc,"3"对应的字符串是def。a对应def，b对应def，c对应def。从而产生最后结果["ad","ae","af","bd","be","bf","cd","ce","cf"]。

题解

首先对于这道题目，我们需要解决的问题有三：

数字与字母的映射如何处理
无法直接使用暴力破解，需要使用其它方法代替
除了2-9的异常按键如何处理

首先处理字母与数字的映射问题，我们可以使用map或者使用数组进行映射。这里我使用的是一维数组进行了映射。
由于使用暴力的多个for无法解决，因此转而采用回溯方法来进行处理。使用回溯三部曲。
1. 确定回溯函数
- 字符串s收集叶子节点，字符串数组保存结果。还需要一个记录遍历digits的index。
1. 确定终止条件
- 当(index == digits.size())时，即遍历结束后，结束回溯。
1. 确定单层遍历逻辑
- 将digit对应的字符转换成int类型，根据数字找到它在phone中的映射
- 用for来处理横向遍历，用递归进行纵向遍历，用pop_back()进行回溯。
回溯问题可以通过树的形式表现出来，具体的可通过下方图片与代码实现深入理解

class Solution {
private:
    const string phone[10] {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
public:
    vector<string> res;
    string s;

    void backtracking(string& digits,int index) {
        // 终止条件
        if (digits.size() == index) {
            res.push_back(s);
            return;
        }

        //字符转换为数字
        int digit = digits[index] - '0';
        // 通过对应的数字找到映射的字母
        string Letters = phone[digit];

        // 横向遍历
        for (int i = 0;i < Letters.size(); i++) {
            // 存入字母
            s.push_back(Letters[i]);
            // 递归，纵向遍历，index+1指向下一层数字
            backtracking(digits,index+1);
            // 返回上一层，即回溯
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        res.clear();

        if (digits.size() == 0) return res;

        backtracking(digits,0);
        return res;
    }
};

Rabbet

电话号码组合

问题描述

输入输出样例

题解