leetcode hot100【LeetCode 17.电话号码的字母组合】java实现

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

题目描述

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

说明:

  • 给定数字 2-9,每个数字对应的字母集合如下:
    • 2 -> “abc”
    • 3 -> “def”
    • 4 -> “ghi”
    • 5 -> “jkl”
    • 6 -> “mno”
    • 7 -> “pqrs”
    • 8 -> “tuv”
    • 9 -> “wxyz”

示例 1:

输入: "23"
输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

示例 2:

输入: ""
输出: []

Java 实现解法

import java.util.ArrayList;
import java.util.List;public class Solution {private static final String[] MAPPING = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if (digits == null || digits.length() == 0) {return result;}backtrack(result, new StringBuilder(), digits, 0);return result;}private void backtrack(List<String> result, StringBuilder current, String digits, int index) {// 如果当前字符串长度等于 digits 长度,说明找到一个完整的组合if (current.length() == digits.length()) {result.add(current.toString());return;}// 获取当前数字对应的字母集合String letters = MAPPING[digits.charAt(index) - '0'];for (char letter : letters.toCharArray()) {current.append(letter);  // 选择当前字母backtrack(result, current, digits, index + 1);  // 递归处理下一个数字current.deleteCharAt(current.length() - 1);  // 回溯,移除当前字母}}
}

解题思路

  1. 问题分析

    • 每个数字都对应着一定的字母集合,问题就是要找到所有这些字母组合的排列。
    • 我们可以通过回溯来解决这个问题。每当处理一个数字时,我们从它对应的字母集合中选择一个字母,然后继续处理下一个数字。
    • 当处理完所有数字时,就找到了一个完整的字母组合。
  2. 回溯法

    • 递归:我们从字符串的第一个数字开始,递归地选择每个数字的字母,直到所有数字都被处理完。每一次递归,我们将当前选中的字母加入到当前的组合中。
    • 回溯:在递归回到上一层时,我们撤销上一步选择的字母,继续尝试其他可能的字母组合。
  3. 实现步骤

    • 定义一个映射数组 MAPPING,表示每个数字对应的字母集合。
    • 使用回溯法逐步构建所有的字母组合,直到遍历完所有数字。
    • 如果字符串为空,直接返回一个空的结果列表。

复杂度分析

  • 时间复杂度O(3^m×4^n),其中m是输入中对应3个字母的数字个数(包括数字 2、3、4、5、6、8),n是输入中对应4个字母的数字个数(包括数字
    7、9),m+n是输入数字的总个数。当输入包含m个对应3个字母的数字和n个对应4个字母的数字时,不同的字母组合一共有3^m×4^n种,需要遍历每一种字母组合。

  • 空间复杂度::O(m+n),其中 m 是输入中对应3个字母的数字个数,n 是输入中对应4个字母的数字个数,m+n是输入数字的总个数。递归调用层数最大为 m+n`

输入示例

digits = "23"

回溯算法执行过程

初始化
  • 映射数组: MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] 对应:

    • 2 -> “abc”
    • 3 -> “def”
  • 递归函数 backtrack(result, current, digits, index)

    • result:存储所有生成的字母组合
    • current:当前的字母组合(StringBuilder
    • digits:输入的数字字符串
    • index:当前正在处理的数字的索引
第一次递归(index = 0,处理数字 ‘2’)
  • 当前 digits 是 “23”,从 index = 0 开始。
  • MAPPING[2] = "abc",所以我们从 'a', 'b', 'c' 中选择。
选择 ‘a’:
  • 当前组合 current = "a",递归到下一层,处理 index = 1(即数字 ‘3’)。
第二次递归(index = 1,处理数字 ‘3’)
  • 当前数字是 ‘3’,MAPPING[3] = "def",所以我们从 'd', 'e', 'f' 中选择。
选择 ‘d’:
  • 当前组合 current = "ad",递归到下一层,处理完所有数字(index = 2,超过了 digits 的长度)。

  • 添加 "ad" 到结果集 result = ["ad"]

选择 ‘e’:
  • 当前组合 current = "ae",递归到下一层,处理完所有数字。

  • 添加 "ae" 到结果集 result = ["ad", "ae"]

选择 ‘f’:
  • 当前组合 current = "af",递归到下一层,处理完所有数字。

  • 添加 "af" 到结果集 result = ["ad", "ae", "af"]

  • 回溯到上一层,撤销选择 ‘f’,恢复 current = "a"

回到第一次递归,选择 ‘b’(index = 0)
  • 当前组合 current = "b",递归到下一层,处理数字 ‘3’(即 index = 1)。
第二次递归(index = 1,处理数字 ‘3’)
  • MAPPING[3] = "def",从 'd', 'e', 'f' 中选择。
选择 ‘d’:
  • 当前组合 current = "bd",递归到下一层,处理完所有数字。

  • 添加 "bd" 到结果集 result = ["ad", "ae", "af", "bd"]

选择 ‘e’:
  • 当前组合 current = "be",递归到下一层,处理完所有数字。

  • 添加 "be" 到结果集 result = ["ad", "ae", "af", "bd", "be"]

选择 ‘f’:
  • 当前组合 current = "bf",递归到下一层,处理完所有数字。

  • 添加 "bf" 到结果集 result = ["ad", "ae", "af", "bd", "be", "bf"]

  • 回溯到上一层,撤销选择 ‘f’,恢复 current = "b"

回到第一次递归,选择 ‘c’(index = 0)
  • 当前组合 current = "c",递归到下一层,处理数字 ‘3’(即 index = 1)。
第二次递归(index = 1,处理数字 ‘3’)
  • MAPPING[3] = "def",从 'd', 'e', 'f' 中选择。
选择 ‘d’:
  • 当前组合 current = "cd",递归到下一层,处理完所有数字。

  • 添加 "cd" 到结果集 result = ["ad", "ae", "af", "bd", "be", "bf", "cd"]

选择 ‘e’:
  • 当前组合 current = "ce",递归到下一层,处理完所有数字。

  • 添加 "ce" 到结果集 result = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce"]

选择 ‘f’:
  • 当前组合 current = "cf",递归到下一层,处理完所有数字。

  • 添加 "cf" 到结果集 result = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

  • 回溯到上一层,撤销选择 ‘f’,恢复 current = "c"

最终结果

回溯到最顶层,所有递归结束,最终生成的所有字母组合为:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

总结

  • 通过回溯算法,我们从每个数字开始,逐步选择它对应的字母,然后递归生成所有的字母组合。
  • 每次递归结束后,我们通过回溯撤销之前的选择,继续探索其他可能的组合。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

重建大师7.0 | 质效全面提升,塑造更优质的实景三维重建

在大势智慧“AI智算、国产信创”2024秋季新品发布会上&#xff0c;重建大师7.0版以其卓越性能惊艳登场。这一新版本不仅引入了创新的倾斜高斯泼溅方法&#xff08;OPGS&#xff09;&#xff0c;实现城市级场景的高效三维重建。 针对传统倾斜建模方法&#xff0c;重建大师7.0同…

Unity性能优化5【物理篇】

1.刚体的碰撞检测属性首选离散型 离散碰撞的缺点是小物体快速移动时&#xff0c;有丢失碰撞的风险。此下拉菜单中&#xff0c;越下面的选项碰撞检测频率越高&#xff0c;性能消耗也显著增加。因此在选择碰撞检测类型时尽量选择离散型。 2.优化碰撞矩阵 合理标记碰撞矩阵可以减…

【threejs】创建及管理场景内的后期处理效果(以bloom为例,开箱即用)

场景内使用 //创建后期通道this.effectManager new EffectManager({ renderer, camera, scene, dom })//循环渲染// 动画----------effect为我控制后期特效的开关animate() {requestAnimationFrame(this.animate);let { camera, controls, effectManager, effect } thisif (!…

建立用邻接表表示的无向图

创建一个建立用邻接表表示的无向图 #include<stdio.h> #include<stdlib.h> typedef struct node {int adjvex;struct node *next; }Anode; typedef struct {char vertex;Anode *link; }Unode; typedef struct {Unode adjlist[100];int vexnum,arcnum; }Adjgraph; …

芯片需要按一下keyup或者复位按键虚拟或者下载之后芯片能下载却运行不了或者需要额外供电。

这些问题很有可能是因为外围电路器件幅值与设计不同的存在&#xff0c;导致你需要外部供电才能实现一个正常运行&#xff0c;可以检查一下外围电路在供电区域的电流区&#xff0c;电阻幅值是否和原理图设计时看的一模一样或者直接更换 因为按键会失灵&#xff0c;首先检查复位按…

Java直播系统视频聊天系统小程序源码

直播视频聊天系统✨&#xff1a;打造你的专属互动空间 &#x1f680; 引言&#xff1a;直播视频聊天系统的兴起 在这个快节奏的数字时代&#xff0c;直播和视频聊天已成为我们日常沟通的重要工具。从游戏直播到在线教育&#xff0c;从远程办公到家庭聚会&#xff0c;直播视频…

云轴科技ZStack助力新远科技开启化工行业智能制造新篇章

新远科技基于云轴科技ZStack Cube超融合和ZStack Zaku容器云平台打造了灵活高效的IT基础设施&#xff0c;实现了IaaS和PaaS层的全面覆盖&#xff0c;优化了资源利用率&#xff0c;降低了硬件成本和运维复杂性&#xff0c;同时强化了数据安全和业务连续性。 化工行业的数字化先…

软件测试PO模式

V1&#xff1a;不使用任何设计模式和单元测试框架 V2&#xff1a;使用UnitTest管理用例 V3&#xff1a;使用方法封装的思想&#xff0c;对代码进行优化 V4&#xff1a;采用PO模式的分层思想对代码进行拆分 V5&#xff1a;对PO分层之后的代码继续优化 V6&#xff1a;PO模式深入封…

网页版五子棋——匹配模块(客户端开发)

前一篇文章&#xff1a;网页版五子棋——用户模块&#xff08;客户端开发&#xff09;-CSDN博客 目录 前言 一、前后端交互接口设计 二、游戏大厅页面 1.页面代码编写 2.前后端交互代码编写 3.测试获取用户信息功能 结尾 前言 前面文章介绍完了五子棋项目用户模块的代码…

Spring设计模式

设计模式 是一种软件开发中的解决方案&#xff0c;设计原则。目的是使代码具有扩展性&#xff0c;可维护性&#xff0c;可读性&#xff0c;如&#xff1a; 单例模式&#xff08;Singleton Pattern&#xff09; Spring IoC 容器默认会将 Bean 创建为单例&#xff0c;保证一个类…

【设计模式】结构型模式(一):适配器模式、装饰器模式

结构型模式&#xff08;一&#xff09;&#xff1a;适配器模式、装饰器模式 1.适配器模式&#xff08;Adapter&#xff09;2.装饰器模式&#xff08;Decorator&#xff09;2.1 主要特点2.2 组成部分2.3 示例代码2.3.1 Component 组件2.3.2 ConcreteComponent 具体组件2.3.3 Dec…

Go Energy 跨平台(GUI)应用编译和安装包制作

构建打包 energy cli 平台介绍描述windowNSIS安装包制作工具可通过 energy cli 安装linuxdpkg 命令系统自带macosenergy 仅生成 xxx.app系统自带 安装包制作 config/energy_[os].json是初始化应用时自动生成的应用配置文件&#xff0c;在编译和制作应用安装包时使用 Windows…

【Linux】进程信号全攻略(二)

&#x1f308; 个人主页&#xff1a;Zfox_ &#x1f525; 系列专栏&#xff1a;Linux 目录 一&#xff1a;&#x1f525; 再谈信号的捕捉 &#x1f98b; 关于信号捕捉的细节部分&#xff08;sigaction函数&#xff09; 二&#xff1a;&#x1f525; 穿插话题 - 操作系统是怎么运…

鸿蒙的进击之路

1. 题记&#xff1a; 为什么要写鸿蒙&#xff0c;因为她是华为的&#xff0c;为什么是华为就要写&#xff0c;因为华为背负了国人太多太多的包袱&#xff0c;或点赞或抨击。 我是强烈支持华为的&#xff0c;但我会客观公正地去评价华为的产品&#xff0c;就比如这篇博文&#…

Swagger的介绍和使用方式+常用注解

介绍: 使用Swagger你只需要按照它的规范去定义接口及接口相关的信息&#xff0c;就可以做到生成接口文档&#xff0c;以及在线接口调试页面.简单来说就是我们只需要知道使用Swagger可以帮助我们后端生成接口文档 Swagger官网:https://swagger.io/ 因为单独使用Swagger会有些…

FFmpeg 4.3 音视频-多路H265监控录放C++开发十三:将AVFrame转换成AVPacket。视频编码,AVPacket 重要函数,结构体成员学习

前提&#xff1a; 从前面的学习我们知道 AVFrame中是最原始的 视频数据&#xff0c;这一节开始我们需要将这个最原始的视频数据 压缩成 AVPacket数据&#xff0c; 我们前面&#xff0c;将YUV数据或者 RGBA 数据装进入了 AVFrame里面&#xff0c;并且在SDL中显示。 也就是说&…

QinQ VLAN技术

QinQ VLAN技术的主要作用包括扩展VLAN数量、实现私网VLAN透传、提供二层隔离和多租户环境等。以下是对这些作用的详细介绍&#xff1a; 扩展VLAN数量 解决VLAN ID不足问题&#xff1a;QinQ技术通过在原有的802.1Q标签基础上再增加一层802.1Q标签&#xff0c;从而将VLAN数量从40…

【机器学习】24. 聚类-层次式 Hierarchical Clustering

1. 优势和缺点 优点&#xff1a; 无需提前指定集群的数量 通过对树状图进行不同层次的切割&#xff0c;可以得到所需数量的簇。树状图提供了一个有用的可视化-集群过程的可解释的描述树状图可能揭示一个有意义的分类 缺点&#xff1a; 计算复杂度较大, 限制了其在大规模数据…

分析报告、调研报告、工作方案等的提示词

什么是提示词&#xff1f; 提示词的英文是Prompt&#xff0c;是你与人工智能&#xff08;AI&#xff09;进行交流的方式。简单来说&#xff0c;提示词就是你给AI的一段文字或问题&#xff0c;AI根据这段文字或问题来生成回应或完成任务。 举个例子&#xff1a;假设你在使用一…

Sentinel通过限流对微服务进行保护

目录 雪崩问题 解决雪崩问题的方法&#xff1a; 我们使用sentinel组件实现微服务的保护 一&#xff1a;下载sentinel 二.启动sentinel 三.访问&#xff1a;localhost:8080 默认的账号和密码都是sentinel 微服务整合sentinel 一.导入sentinel依赖 二.在application.yml配…