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

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

发布时间:2023/6/3 16:33:10

文章目录

  • 题目: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+1map<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);}}
};

本文链接:https://www.ngui.cc/51cto/show-209.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000