当前位置：网站首页>leetcode 17. Letter Combinations of Phone Numbers

leetcode 17. Letter Combinations of Phone Numbers

2022-08-06 03:01:00 【_Liu Xiaoyu】

作者简介：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”]

🧡 算法分析

This method is to usedfs

下图解释dfs遍历过程（类似）：
在这里插入图片描述

算法步骤:

Iterate over which character appears in the first position
深度 + 1, Strings concatenated at the same time + 1, Check whether the length is equal to the length of the original string in the front
详见代码

代码实现

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'])  // Traversing what the current bit can take
            {
    
                dfs(s, u + 1, path + c);
            }
        }
    }
};