首页 > 编程学习 > 【LeetCode】17. 电话号码的字母组合

【LeetCode】17. 电话号码的字母组合

发布时间:2022/1/17 12:12:25

文章目录

  • 题目:17. 电话号码的字母组合
  • 解题思路
  • 代码

题目:17. 电话号码的字母组合

17. 电话号码的字母组合

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

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

在这里插入图片描述

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

解题思路

  1. 设置一个map,用于存放数字对应的字母,记录总结果的字符串数组res。设置一个和数字等长的字符串tmp,用于记录每轮结果;
  2. dfs函数中,传入参数(记录字符串长度的k,记录每轮字符串的tmp,数字串digits)
  3. 递归终止条件:k==数字长度
  4. 递归过程:
    1. 取出map中数字对应的字母串
    2. 遍历字母串,令tmp的第k个字符等于当前字母
    3. 下一轮递归,k+1

代码

class Solution {
public:
// 1. 设置一个map,用于存放数字对应的字母,记录总结果的字符串数组res。设置一个和数字等长的字符串tmp,用于记录每轮结果;
// 2. dfs函数中,传入参数(记录字符串长度的k,记录每轮字符串的tmp,数字串digits)
// 3. 递归终止条件:k==数字长度
// 4. 递归过程:
//  1. 取出map中数字对应的字母串
// 	2. 遍历字母串,令tmp的第k个字符等于当前字母
// 	3. 下一轮递归,k+1
    map<char,string> map{
        {'2', "abc"}, 
        {'3', "def"}, 
        {'4', "ghi"}, 
        {'5', "jkl"}, 
        {'6', "mno"}, 
        {'7', "pqrs"}, 
        {'8', "tuv"}, 
        {'9', "wxyz"}
    };
    vector<string> res;
    vector<string> letterCombinations(string digits) {
        if (digits == "") return res;
        string tmp(digits.size(),' ');
        dfs(tmp, 0, digits);
        return res;
    }

    void dfs(string tmp, int k,string digits) {
        if (k == digits.size()) {
            res.push_back(tmp);
            return ;
        }
        string s = map[digits[k]];
        for (char ch:s) {
            tmp[k] = ch;
            dfs(tmp, k + 1, digits);
        }
    }
};
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000