leetcode 17. 电话号码的字母组合

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

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

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

示例1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例2：

输入：digits = “”
输出：[]

示例3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

🧡 算法分析

此题方法是用dfs

下图解释dfs遍历过程（类似）：

算法步骤:

1. 遍历第一个位置出现哪个字符
2. 深度 + 1， 同时拼接的字符串 + 1， 在前面判断长度是否等于原字符串的长度
3. 详见代码

💚 代码实现

class Solution {
public:
    vector<string> ans;

    string strs[10] = {
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz",
    };

    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return ans;
        dfs(digits, 0, "");
        return ans;
    }

    void dfs(string s, int u, string path)
    {
        if(u == s.size()) ans.push_back(path);
        else 
        {
            for(auto c : strs[s[u] - '0'])  // 遍历当前这一位可以取哪些
            {
                dfs(s, u + 1, path + c);
            }
        }
    }
};
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

执行结果：

💙 时间复杂度分析

根据最长的字符串长度，dfs时间复杂度为O(4ⁿ)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！