【力扣-回溯】2、电话号码的字母组合（17） 17 电话号

发表于

「这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战」

17. 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

示例 1：

1
2
arduino复制代码输入： digits = "23"
输出： ["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
ini复制代码输入： digits = ""
输出： []

示例 3：

1
2
arduino复制代码输入： digits = "2"
输出： ["a","b","c"]

解析

回溯法

  • 首先需要一个字符串数组vector<string> result来存放结果，同时还需要一个字符串s来存放叶子结点的值
  • 确定递归函数的参数和返回值
    • 参数：字符串，指向数字的索引（用来统计访问到第几个数,index在这里该表示树的深度）
  • 确定终止条件
    • 如果index 等于输入的数字个数digits.size()，则将s添加到结果集result中
  • 确定单层循环的逻辑
    • 取Index指向的数字，找到对应的字符串
    • for循环处理这个字符串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
c++复制代码class Solution
{
public:

    vector<string> letterCombinations(string digits)
    {
        // 如果字符串为空，直接返回
        if (digits == "")
        {
            return result;
        }
        // 进行回溯处理
        backtracking(digits,0);
        return result;
    }

private:
    // 结果集
    vector<string> result;
    // 记录叶子节点
    string s;
    // 定义数字和字符串的映射
    // 采用字符串数组来存储
    const string letterMap[10] = {
        "",     //0
        "",     //1
        "abc",  //2
        "def",  //3
        "ghi",  //4
        "jkl",  //5
        "mno",  //6
        "pqrs", //7
        "tuv",  //8
        "wxyz", //9

    };
    // 这里的index不是 组合问题里面的 startIndex
    // index指向数字，表示遍历到第几个数字了，还表示树的深度
    void backtracking(const string &digits, int index)
    {
        // index等于字符串的大小时
        // 说明找到了匹配的，添加到结果集中
        if (index == digits.size())
        {
            result.push_back(s);
            return;
        }

        // 将index指向的数字转换成int类型
        int digit = digits[index] - '0';
        // 取出数字对应的字符串
        string letter = letterMap[digit];
        // 对字符串进行遍历
        for (int i = 0; i < letter.size(); i++)
        {
            s.push_back(letter[i]);
            // 下一层处理下一个数字
            backtracking(digits, index + 1);
            s.pop_back(); // 回溯
        }
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%