力扣17. 电话号码的字母组合(java 回溯法)

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

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路

题目给定一串数字,要求我们找出所有可能的字母组合,即我们可以穷举出所有可能的结果,而涉及到穷举我们自然可以想到利用回溯来解决问题,在本题目中我们选择给定字符串digits中的每一个字符作为决策阶段,具体的:

1.我们先创建一个哈希表将数字与其对应的字符存入(数字作为键,所有的字符作为值)
2.编写,并调用回溯函数,当决策阶段等于digits的长度时,将当前的决策路径添加到结果集合中,否则从digits字符串的第一个字符开始回溯调用!

解题方法

1.创建结果集合result,若当digits为空时,返回空集合;
2.创建一个String类型的数组mappings作为哈希表,索引从0-9,用于存储数字与其字符的对应关系,其中数字索引作为键,所有的字符作为值;
3.创建一个char类型的数组,数组长度为digits字符串的长度,作为回溯过程中的决策路径
4.编写并调用回溯函数,参数列表为(String[] mappings, String digits, int k, char[] path),其中由参数mappings 与digits决定参数列表,k表示决策阶段,path表示决策路径

4.1若k等于digits的长度时,表示找到一个字母组合,则将其添加到结果集合result中,
4.2先得到当前决策阶段的digits中的数字字符,再通过我们创建的哈希表mappins找出该数字字符对应的所有字母字符
4.3以当前的数字字符对应得所有字母字符开始,遍历所有得字母字符并开始回溯调用

注意:在上述解题方法中我们没有显示地在回溯调用后将当前的决策阶段状态还原(回溯的本质就是一个多状态转移)但这并不表示我们没有实现该操作,而是因为:我们定义的决策阶段是一个char类型的数组,再回溯递归的调用过程中会将原来索引位置上的值给覆盖掉,以达到恢复当前决策阶段的操作

复杂度

时间复杂度:

最坏时间复杂度: O ( 3 m × 4 n ) O(3^m \times 4^n) O(3m×4n),其中m表示选择对应只有三个字母的数字的个数,n表示对应四个字母的个数

空间复杂度:

O ( n + m ) O(n + m) O(n+m)

Code

class Solution {
    //Result list
    private List<String> result = new ArrayList<>();

    /**
     * Get the all possible combinations
     *
     * @param digits The combination given by topic
     * @return List<String>
     */
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return Collections.emptyList();
        }
        //Create the reflection
        String[] mappings = new String[10];
        mappings[2] = "abc";
        mappings[3] = "def";
        mappings[4] = "ghi";
        mappings[5] = "jkl";
        mappings[6] = "mno";
        mappings[7] = "pqrs";
        mappings[8] = "tuv";
        mappings[9] = "wxyz";
        //Decision path
        char[] path = new char[digits.length()];
        backtrack(mappings, digits,0, path);
        return result;
    }

    /**
     * Use backtracking to find all possible combinations
     *
     * @param mappings Mapping between letters and numbers
     * @param digits   Combination of numbers given by topic
     * @param k        Decision stage
     * @param path     Decision path
     */
    private void backtrack(String[] mappings, String digits, int k, char[] path) {
        //End condition
        if (k == digits.length()) {
            result.add(new String(path));
            return;
        }
        String mapping = mappings[digits.charAt(k) - '0'];
        for (int i = 0; i < mapping.length(); ++i) {
            path[k] = mapping.charAt(i);
            backtrack(mappings, digits, k + 1, path);
        }
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

我的NPI项目之Android 安全系列 -- Android Strongbox 初识

从Android9(Pie)开始,Google强烈建议支持Strongbox. 具体描述如下: 一直到目前的Android14. 对应的内容也一并贴出来: 说人话就是Android开始通过独立于主SoC的单元进行密钥存储了。 通常&#xff0c;这样的单元就是我们通常称作的Secure Element&#xff08;SE&#xff09;&am…

5分钟搞懂K8S Pod Terminating/Unknown故障排查

Kubernetes集群中的Pod有时候会进入Terminating或Unknown状态&#xff0c;本文列举了6种可能的原因&#xff0c;帮助我们排查这种现象。原文: K8s Troubleshooting — Pod in Terminating or Unknown Status 有时我们会看到K8S集群中的pod进入"Terminating"或"U…

FFmpeg-基础组件-AVFrame

本章主要介绍FFmpeg基础组件AVFrame. 文章目录 1.结构体成员2.成员函数AVFrame Host内存的获取 av_frame_get_bufferAVFrame device内存获取av_hwframe_get_buffer&#xff08;&#xff09; 1.结构体成员 我们把所有的代码先粘贴上来&#xff0c;在后边一个一个解释。 typede…

基于ssm办公用品管理系统开发与设计论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本办公用品管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…

HashData:大数据时代的“追光者”

12月7日—9日&#xff0c;2023中国光电子产业集群大会暨光电交易博览会在武汉光谷科技会展中心举办。酷克数据作为国内云数仓领军企业&#xff0c;受邀出席本次大会。 在会上&#xff0c;酷克数据展示了云数仓领域最新前沿技术以及HashData云数仓在行业应用落地方案与实践案例…

【SpringBoot教程】SpringBoot 实现前后端分离的跨域访问(Nginx)

作者简介&#xff1a;大家好&#xff0c;我是撸代码的羊驼&#xff0c;前阿里巴巴架构师&#xff0c;现某互联网公司CTO 联系v&#xff1a;sulny_ann&#xff08;17362204968&#xff09;&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗…

【docker】Hello World

搜索hello-world镜像 docker search hello-world拉去镜像 docker pull hello-world查看本地镜像 docker images 运行镜像 docker run hello-world查看所有的容器 docker ps -a查询start状态容器 docker ps 输出介绍 CONTAINER ID: 容器 ID。IMAGE: 使用的镜像。COMMAN…

基于正交偶极子的四元数MUSIC算法及其Matlab代码

目录 引言信源数估计MUSIC算法基于正交偶极子的MUSIC算法正交偶极子模型正交偶极子的阵列接受模型基于正交偶极子的MUSIC算法模值约束法求极化信息 基于正交偶极子的四元数MUSIC算法四元数的阵列接受模型四元数MUSIC算法 引言 本文介绍了空间谱估计中的信源数估计、MUSIC算法、…

基于ssm电脑配件销售系统的设计与实现论文

摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于电脑配件销售系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了电脑配件销售系统&#xff0c;它彻底改变了过…

Django 模型操作-分页(七)

一、连接MySql数据库 1、先安装MySQL 2、再安装MySQL驱动 使用mysqlclient pip install mysqlclient 如果上面的命令安装失败, 则尝试使用国内豆瓣源安装: pip install -i https://pypi.douban.com/simple mysqlclient 二、在settings.py中配置 三、 book表的数据…

多模态AI产业链全景梳理

当前AI模型从单模态向多模态演进&#xff0c;有望实现认知智能&#xff0c;是AI未来发展的明确趋势。近期 AI 多模态模型不断取得突破性进展。OpenAI 于11 月发布了 GPT-4 Turbo 且开放了 GPTs再次颠覆行业&#xff0c;GPTs短期上线数量已超3万&#xff0c;揭开AIGC应用生态序幕…

CSS 实现无缝滚动

效果展示 CSS 知识点 animation 综合运用 页面整体布局 <div class"scroll" style"--t: 20s"><div><span>HTML</span><span>CSS</span><span>JavaScript</span><span>React</span><spa…

WEB 3D技术 以vue3+vite环境为例 讲解vue项目中使用three

上文 WEB 3D 技术&#xff0c;通过node环境创建一个three案例 中 我们打造了自己的第一个Web 3D界面 那么 今天 我们就来结合vue来开发我们的3D界面 这里 我们先创建一个文件夹 作为文件目录 千万不要放C盘 我们 依旧是在终端执行命令 npm init vitelatest输入一下项目名称 …

自动驾驶学习笔记(十七)——视觉感知

#Apollo开发者# 学习课程的传送门如下&#xff0c;当您也准备学习自动驾驶时&#xff0c;可以和我一同前往&#xff1a; 《自动驾驶新人之旅》免费课程—> 传送门 《Apollo 社区开发者圆桌会》免费报名—>传送门 文章目录 前言 分类 目标检测 语义分割 实例分割 …

uniapp中使用 unicloud

一、新建一个带有unicloud 二、创建一个服务空间 1. 右键uniCloud&#xff0c;关联云服务空间 我当前没有服务空间&#xff0c;需要新建一个服务空间&#xff0c;之后将其关联。初始化服务空间需要的时间有点长 服务空间初始化成功后&#xff0c;刷新HBuilder&#xff0c;勾选…

数字图像处理(实践篇)二十 人脸特征提取

目录 1 安装face_recognition 2 涉及的函数 3 实践 使用face_recognition进行人脸特征提取. 1 安装face_recognition pip install face_recognition 或者 pip --default-timeout100 install face_recognition -i http://pypi.douban.com/simple --trusted-host pypi.dou…

【51单片机系列】矩阵按键扩展实验

本文对矩阵按键的一个扩展&#xff0c;利用矩阵按键和动态数码管设计一个简易计算器。代码参考&#xff1a;https://blog.csdn.net/weixin_47060099/article/details/106664393 实现功能&#xff1a;使用矩阵按键&#xff0c;实现一个简易计算器&#xff0c;将计算数据及计算结…

15Linux、GIT及相关相似面试题、PostMan

Linux和git相似是命令相关的层次结构相似 Linux Linux Linux常用操作_linux操作-CSDN博客 程序员常用的10个Linux命令_简介linux系统中的10个常用命令及功能-CSDN博客 help help 命令 &#xff1a;获得 shell 内置命令的帮助信息&#xff0c;常用形式 help cd ls --help …

SPI 通信-stm32入门

本节我们将继续学习下一个通信协议 SPI&#xff0c;SPI 通信和我们刚学完的 I2C 通信差不多。两个协议的设计目的都一样&#xff0c;都是实现主控芯片和各种外挂芯片之间的数据交流&#xff0c;有了数据交流的能力&#xff0c;我们主控芯片就可以挂载并操纵各式各样的外部芯片&…

SpringBoot+Netty+Websocket实现消息推送

这样一个需求&#xff1a;把设备异常的状态每10秒推送到页面并且以弹窗弹出来&#xff0c;这个时候用Websocket最为合适&#xff0c;今天主要是后端代码展示。 添加依赖 <dependency><groupId>io.netty</groupId><artifactId>netty-all</artifact…