力扣第十七题——电话号码的字母组合

内容介绍

给定一个仅包含数字 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'] 的一个数字。

完整代码

 class Solution {public List<String> letterCombinations(String digits) {List<String> combinations = new ArrayList<String>();if (digits.length() == 0) {return combinations;}Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};backtrack(combinations, phoneMap, digits, 0, new StringBuffer());return combinations;}public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {if (index == digits.length()) {combinations.add(combination.toString());} else {char digit = digits.charAt(index);String letters = phoneMap.get(digit);int lettersCount = letters.length();for (int i = 0; i < lettersCount; i++) {combination.append(letters.charAt(i));backtrack(combinations, phoneMap, digits, index + 1, combination);combination.deleteCharAt(index);}}}
}

思路详解

1. 初始化返回列表
List<String> combinations = new ArrayList<String>();

创建一个空列表combinations,用于存储所有可能的字母组合。

2. 检查输入字符串是否为空
if (digits.length() == 0) {return combinations;
}

如果输入的数字字符串为空,则直接返回空列表。

3. 创建电话键盘映射
Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");
}};

使用一个HashMap来存储电话键盘上的数字到对应字母的映射。

4. 调用回溯函数
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());

调用backtrack函数来填充combinations列表,从索引0开始,并使用一个StringBuffer来构建当前的字母组合。

5. 定义回溯函数
public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {

backtrack是一个递归函数,用于生成所有可能的字母组合。

6. 回溯终止条件
if (index == digits.length()) {combinations.add(combination.toString());
}

index等于digits的长度时,表示一个完整的组合已经构建完成,将其添加到combinations列表中。

7. 构建组合
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {combination.append(letters.charAt(i));backtrack(combinations, phoneMap, digits, index + 1, combination);combination.deleteCharAt(index);
}

对于当前数字digit,获取其对应的字母字符串letters,然后遍历这些字母:

  • 将当前字母添加到combination中。
  • 递归调用backtrack函数,将index加1,表示向组合中添加下一个字母。
  • 在递归返回后,移除combination中最后一个添加的字母,以便尝试下一个字母。

知识点精炼

总结 

该代码通过回溯算法生成所有可能的字母组合。回溯是一种试探性的算法,它在每一步都尝试所有可能的选择,并在达到某个条件时回退到上一步,尝试其他选择。在电话键盘字母组合的问题中,回溯算法通过递归地构建每个数字对应的字母组合,最终生成所有可能的组合。

  1. 递归与回溯

    • 使用递归函数backtrack实现回溯算法,这是一种通过不断尝试所有可能的选择来找到所有解的算法。
  2. 映射关系

    • 利用HashMap建立数字到字母的映射关系,方便根据输入的数字找到对应的字母组合。
  3. 字符串处理

    • 使用StringBuffer来动态构建字符串,它比普通字符串更高效,因为它允许修改。
  4. 递归终止条件

    • 当递归的深度等于输入数字字符串的长度时,表示已经构建了一个完整的组合,此时将组合添加到结果列表中。
  5. 循环与递归结合

    • 在递归函数中,通过一个循环遍历当前数字对应的每个字母,并在每次循环中递归调用自身。
  6. 状态重置

    • 在递归返回后,通过combination.deleteCharAt(index)撤销上一次的选择,以便尝试其他可能的字母。
  7. 参数传递

    • 递归函数中通过参数传递当前的状态,包括结果列表、映射表、输入字符串、当前索引和当前组合。
  8. 边界条件检查

    • 在主函数letterCombinations中,首先检查输入字符串是否为空,为空则直接返回空列表。
  9. 时间复杂度

    • 算法的时间复杂度是O(4^n),其中n是输入字符串的长度,因为每个数字最多对应4个字母。
  10. 空间复杂度

    • 空间复杂度主要取决于递归调用的深度和结果列表的大小,最坏情况下为O(4^n)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/379735.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

iredmail服务器安装步骤详解!如何做配置?

iredmail服务器安全性设置指南&#xff1f;怎么升级邮件服务器&#xff1f; iredmail是一个功能强大的邮件服务器解决方案&#xff0c;它集成了多个开源软件&#xff0c;使您能够快速部署和管理邮件服务。AokSend将逐步引导您完成安装过程&#xff0c;无需深入的编程知识即可轻…

【ai】学习笔记:电影推荐1:协同过滤 TF-DF 余弦相似性

2020年之前都是用协同过滤2020年以后用深度学习、人工智能视频收费的,不完整,里面是电影推荐 这里有个视频讲解2016年大神分析了电影推荐 :MovieRecommendation github地址 看起来是基于用户的相似性和物品的相似性,向用户推荐物品: 大神的介绍: 大神的介绍: 基于Pytho…

海外营销推广:快速创建维基百科(wiki)词条-大舍传媒

一、维基百科的永久留存问题 许多企业和个人关心维基百科是否能永久留存。实际上&#xff0c;只要企业和个人的行为没有引起维基百科管理方的反感&#xff0c;词条就可以长期保存。如果有恶意行为或被投诉&#xff0c;维基百科可能会对词条进行删除或修改。 二、创建维基百科…

Python项目打包与依赖管理指南

在Python开发中&#xff0c;python文件需要在安装有python解释器的计算机的电脑上才能运行&#xff0c;但是在工作时&#xff0c;我们需要给客户介绍演示项目功能时并不一定可以条件安装解释器&#xff0c;而且这样做非常不方便。这时候我们可以打包项目&#xff0c;用于给客户…

平价养猫必看!测评几十款选出的最值得入手的希喂主食冻干

各位铲屎官&#xff0c;今天来聊聊我近期发现的宝藏主食冻干——希喂CPMR2.0大橙罐。平价养猫必看&#xff01;&#xff0c;在追求猫咪饮食健康与自身预算平衡的路上&#xff0c;我尝试了多种产品&#xff0c;而希喂以其高含肉量和高营养价值脱颖而出。它让喂食变得多样化且高效…

【STM32】LED闪烁LED流水灯蜂鸣器(江科大)

LED正极&#xff1a;外部长脚、内部较小 LED负极&#xff1a;外部短脚、内部较大 LED电路 限流电阻&#xff1a;保护LED&#xff0c;调节LED亮度&#xff08;本实验用面包板为了方便&#xff0c;省去了限流电阻&#xff0c;设计电路时要加上&#xff09; 左上图&#xff1a;低…

【golang-ent】go-zero框架 整合 ent orm框架 | 解决left join未关联报错的问题

一、场景 1、子表&#xff1a;cp_member_point_history cp_member_point_history表中字段&#xff1a;cp_point_reward_id 是cp_point_reward的主键id 当本表中的cp_point_reward_id字段为0&#xff08;即&#xff1a;没有可关联主表的&#xff09; CREATE TABLE cp_member_poi…

“社群+”生态下的开源AI智能名片源码:驱动商业与社会连接的新引擎

摘要&#xff1a;在“社群”生态日益成为主流趋势的今天&#xff0c;开源AI智能名片源码作为技术创新与社群运营的深度融合体&#xff0c;正逐步展现出其重塑商业格局、深化社会连接的巨大潜力。本文旨在深入探讨开源AI智能名片源码的技术特性、在“社群”生态中的具体应用、对…

Java线程池ThreadPoolExecutor原理、源码分析

目录 为什么要使用线程池&#xff1f; 线程池执行任务的具体流程是怎样的&#xff1f; 线程池的五种状态是如何流转的&#xff1f; 线程池中的线程是如何关闭的&#xff1f; 线程池为什么一定得是阻塞队列&#xff1f; 线程发生异常&#xff0c;会被移出线程池吗&#xff…

【产品那些事】固件安全-关于OTA升级包分析

文章目录 前言什么是OTA?升级包(固件)的类型和架构案例tp-link路由器升级包怎么解包分析?binwalk安装及使用ubi_reader安装及使用unsquashfs安装及使用某车企OTA升级包通用Android OTA解包相关分区第二层解包前言 什么是OTA? OTA(Over-the-Air)是一种通过无线通信网络(…

Golang | Leetcode Golang题解之第237题删除链表中的节点

题目&#xff1a; 题解&#xff1a; func deleteNode(node *ListNode) {node.Val node.Next.Valnode.Next node.Next.Next }

华为“铁三角模式”在数据类项目中的应用和价值

引言&#xff1a;随着信息技术的飞速发展&#xff0c;企业纷纷踏上数字化转型的道路&#xff0c;希望通过数据分析和智能决策来提升企业竞争力。在这一过程中&#xff0c;数据类项目成为关键&#xff0c;它们旨在构建高效的数据治理和分析平台&#xff0c;为企业决策提供有力支…

如何打造高效电子邮件流程?附客户生命周期邮件策略!

一个成功的EDM邮件需要包含多个关键元素&#xff0c;从内容、设计到呼唤行动&#xff0c;每个环节都至关重要。今天咱们来聊聊怎么通过电子邮件&#xff0c;帮那些想要出海的中国中小企业吸引更多客户。别小看这一封封邮件&#xff0c;它们可是连接你和客户的秘密武器&#xff…

Qt模型/视图架构——委托(delegate)

一、为什么需要委托 模型&#xff08;model&#xff09;用来数据存储&#xff0c;视图&#xff08;view&#xff09;用来展示数据。因此&#xff0c;模型/视图架构是一种将数据存储和界面展示分离的编程方法。具体如下图所示&#xff1a; 由图可知&#xff0c;模型向视图提供数…

react 快速入门思维导图

在掌握了react中一下的几个步骤和语法&#xff0c;基本上就可以熟练的使用react了。 1、组件的使用。react创建组件主要是类组件和函数式组件&#xff0c;类组件有生命周期&#xff0c;而函数式组件没有。 2、jsx语法。react主要使用jsx语法&#xff0c;需要使用babel和webpa…

C/C++蓝屏整人代码

文章目录 &#x1f4d2;程序效果 &#x1f4d2;具体步骤 1.隐藏任务栏 2.调整cmd窗口大小 3.调整cmd窗口屏幕颜色 4.完整代码 &#x1f4d2;代码详解 &#x1f680;欢迎互三&#x1f449;&#xff1a;程序猿方梓燚 &#x1f48e;&#x1f48e; &#x1f680;关注博主&a…

Spring Web MVC入门(2)(请求2)

目录 1.传递JSON数据 传递JSON对象 2.获取URL中的参数PathVariable 3.上传文件RequestPart 4.获取Cookie/Session (1)获取Cookie 简洁获取Cookie (2)获取Session Sesson读取 简洁获取Session(1) 简洁获取Session(2) 5.获取Header 简洁获取Header 1.传递JSON数据 J…

如何写好建模论文

如何写好建模论文 一、 写好数模答卷的重要性 1.评定参赛队的成绩好坏、高低&#xff0c;获奖级别&#xff0c; 数模答卷&#xff0c; 是唯一依据。 2.答卷是竞赛活动的成绩结晶的书面形式。 3.写好答卷的训练&#xff0c;是科技写作的一种基本训练。 二、 答卷的基本内容&…

从零开始学量化~Ptrade使用教程(六)——盘后定价交易、港股通与债券通用质押式回购

盘后固定价交易 实现科创板、创业板的盘后固定价交易&#xff0c;界面如下显示&#xff1a; 交易 输入科创板或创业板代码&#xff0c;选择委托方向&#xff0c;输入委托价格、委托数量&#xff0c;点击“买入”或“卖出”按钮进行委托。可出现一个委托提示框提示是否继续委托操…

QtC++ 设计模式(五)——状态模式

状态模式 序言理解源码 序言 设计模式只是一个抽象的设计模式方法&#xff0c;并不是一个固定使用的搭配&#xff0c;就算是普通switch语句&#xff0c;Map&#xff0c;乃至状态机都是状态模式的其中一种实现方法 状态模式看起来好像和策略模式差不多&#xff0c;主要是其的侧…