leetcode17 电话号码的字母组合

方法1 if-else方法 

if-else方法的思路及其简单粗暴，如下图所示，以数字234为例，数字2所对应的字母是abc，数字3所对应的是def，数字4所对应的是ghi，最后所产生的结果就类似于我们中学所学过的树状图一样，从左到右的一组一组生成结果，首先取出数字2的第一个索引对应的a，然后紧接着添加数字3对应的第一个索引的字母d，然后再添加数字4所对应的ghi，分别组成adg、adh、adi，然后一直进行排列组合，直到把所有的结果都列举完，那么就程序就执行完了。

python完整代码：

class Solution:def letterCombinations(self, digits):# 获取输入数字串的长度n = len(digits)result = []  # 用于存储最终的字母组合结果if n == 0:return result  # 如果输入为空字符串，则直接返回空列表for i in range(n):self.AddString(result, digits[i])return resultdef AddString(self, result, t):  # 定义一个添加字符串的函数n = len(result)letters = ""if t == '2':letters = "abc"elif t == '3':letters = "def"elif t == '4':letters = "ghi"elif t == '5':letters = "jkl"elif t == '6':letters = "mno"elif t == '7':letters = "pqrs"elif t == '8':letters = "tuv"elif t == '9':letters = "wxyz"if n == 0:result.extend(list(letters))  # 如果结果集为空，直接添加第一个数字对应的字母else:temp_result = []for i in range(n):  # i表示第一个数字所对应的字母的位置for letter in letters:# 将当前结果集中的每个组合与新的字母组合，得到新的结果集temp_result.append(result[i] + letter)result[:] = temp_result  # 用新的结果集替换原有结果集if __name__ == "__main__":solution = Solution()combinations = solution.letterCombinations("234")print(combinations)

c++完整代码： 

#include<iostream>
#include<vector>using namespace std;class Solution{
public:vector<string> letterCombinations(string digits){int n = digits.length();  //获取输入数字串的长度vector<string> result; //用于存储最终的字母组合结果if(n == 0){return result;}for(int i=0;i<n;++i){AddString(result, digits[i]);  // 调用添加字母函数}return result;}
private:void AddString(vector<string>& result, char digit){int n = result.size();string letters = "";if (digit == '2'){letters = "abc";} else if(digit == '3'){letters = "def";} else if(digit == '4'){letters = "ghi";} else if(digit == '5') {letters = "jkl";} else if(digit == '6'){letters = "mno";} else if(digit == '7'){letters = "pqrs";} else if(digit == '8'){letters = "tuv";} else if(digit == '9'){letters = "wxyz";}if (n == 0){for(char letter : letters){result.push_back(string(1, letter));// 如果结果集为空，直接添加第一个数字对应的字母}} else{vector<string> temp_result;for(int i = 0;i < n; ++i){for(char letter : letters){// 将当前结果集中的每个组合与新的字母组合，得到新的结果集temp_result.push_back(result[i] + letter);}}result = temp_result; // 用新的结果集替换原有结果集}}
};int main(){Solution solution;vector<string> combinations = solution.letterCombinations("234");for(const auto& combination : combinations){cout << combination << endl;}return 0;
}

java完整代码：  

import java.util.List;
import java.util.ArrayList;
public class LetterCombinations {public List<String> letterCombinations(String digits) {// 获取输入数字串的长度int n = digits.length();// 用于存储最终的字母组合结果List<String> list = new ArrayList();// 如果输入为空字符串，则直接返回空列表if (n == 0) {return list;}// 遍历每个数字字符for (int i = 0; i < n; i++) {// 调用 StringAdd 函数处理每个数字对应的字母StringAdd(list, digits.charAt(i));}return list;}// 定义一个添加字符串的函数public void StringAdd(List<String> list, char t) {// 获取当前结果集的长度int n = list.size();if(t == '2'){  // 处理数字 2 对应的字母组合if(n==0){list.add("a");list.add("b");list.add("c");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 'a', 'b', 'c'，得到新的结果集list.add(list.get(i)+"a");list.add(list.get(i)+"b");list.add(list.get(i)+"c");}for(int i=0;i<n;i++){list.remove(0);}}// 3}else if(t == '3'){if(n==0){list.add("d");list.add("e");list.add("f");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 'd', 'e', 'f'，得到新的结果集list.add(list.get(i)+"d");list.add(list.get(i)+"e");list.add(list.get(i)+"f");}for(int i=0;i<n;i++){list.remove(0);}}// 4}else if(t == '4'){if(n==0){list.add("g");list.add("h");list.add("i");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 'g', 'h', 'i'，得到新的结果集list.add(list.get(i)+"g");list.add(list.get(i)+"h");list.add(list.get(i)+"i");}for(int i=0;i<n;i++){list.remove(0);}}// 5}else if(t == '5'){if(n==0){list.add("j");list.add("k");list.add("l");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 'j', 'k', 'l'，得到新的结果list.add(list.get(i)+"j");list.add(list.get(i)+"k");list.add(list.get(i)+"l");}for(int i=0;i<n;i++){list.remove(0);}}// 6}else if(t == '6'){if(n==0){list.add("m");list.add("n");list.add("o");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 'm', 'n', 'o'，得到新的结果list.add(list.get(i)+"m");list.add(list.get(i)+"n");list.add(list.get(i)+"o");}for(int i=0;i<n;i++){list.remove(0);}}// 7}else if(t == '7'){if(n==0){list.add("p");list.add("q");list.add("r");list.add("s");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 'p', 'q', 'r', 's'，得到新的结果list.add(list.get(i)+"p");list.add(list.get(i)+"q");list.add(list.get(i)+"r");list.add(list.get(i)+"s");}for(int i=0;i<n;i++){list.remove(0);}}// 8}else if(t == '8'){if(n==0){list.add("t");list.add("u");list.add("v");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 't', 'u', 'v'，得到新的结果list.add(list.get(i)+"t");list.add(list.get(i)+"u");list.add(list.get(i)+"v");}for(int i=0;i<n;i++){list.remove(0);}}// 9}else if(t == '9'){if(n==0){list.add("w");list.add("x");list.add("y");list.add("z");}else{for(int i=0;i<n;i++){// 遍历当前结果集，为每个组合添加 'w', 'x', 'y', 'z'，得到新的结果list.add(list.get(i)+"w");list.add(list.get(i)+"x");list.add(list.get(i)+"y");list.add(list.get(i)+"z");}for(int i=0;i<n;i++){list.remove(0);}}}}public static void main(String[] args){LetterCombinations solution = new LetterCombinations();List<String> combinations = solution.letterCombinations("234");System.out.println(combinations);}
}

方法2 回溯法 

上面我们讨论了通过列举的方法生成结果，但是发现程序写起来实在是太长了，而且看着很low，那么此时我们就可以把数字组合里面每一个数字所对应的字母组合通过一个篮子（哈希表）存起来，要用哪个就拿哪一个，紧接着再通过回溯的方法进行解决，以下是chatgpt所回答的回溯算法：

回溯算法（Backtracking）是一种通过尝试所有可能的候选解并在找到可行解之前放弃部分（或全部）解空间的策略。在问题的解空间中，通过深度优先搜索，一步一步地探索各个可能的解，当发现当前的部分解不能满足问题的约束条件时，就放弃该部分解，回溯到上一步，继续搜索其他可能的解。

回溯算法通常采用递归的方式实现，每一层递归代表问题的一个阶段，通过递归的深入，逐步构建出问题的解。在搜索过程中，如果当前解不满足问题的条件，则回溯到上一步，尝试其他可能的选择。

典型的回溯问题包括组合问题、排列问题、子集问题等。回溯算法通常用于解决组合优化问题，其中问题的解是某种组合的集合，而且问题通常可以分解为多个子问题，通过递归地解决子问题来构建整体的解。

关键特点：

  1. 状态空间树： 回溯算法可以通过状态空间树的形式进行表示，每个节点代表问题的一个阶段，树的每一层对应算法的一个递归调用。
  2. 深度优先搜索： 回溯算法采用深度优先搜索的策略，即一条路走到底，如果发现当前路径不能满足问题的条件，就回溯到上一步。
  3. 剪枝： 在搜索的过程中，可以通过剪枝来减少搜索空间，提高效率。当发现当前部分解无法满足问题的条件时，可以提前结束搜索。

经典的回溯问题包括八皇后问题、0-1背包问题、图的着色问题等。回溯算法的复杂度通常比较高，因此在设计时需要注意优化搜索空间以提高效率。

但是本题不存在不可行的解，所以通过穷举的方法就可以实现。该方法的思路和上述的方法基本上是一致的。

python完整代码：

class Solution:def letterCombinations(self, digits):# 如果输入为空，则直接返回空列表if not digits:return list()# 定义电话号码到字母的映射关系phoneMap = {"2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": "pqrs","8": "tuv","9": "wxyz",}def backtrack(index):# 当前组合字符串长度等于输入数字串长度时，将其加入结果集if index == len(digits):combinations.append("".join(combination))  # 获取当前数字对应的字母集合else:digit = digits[index]  # 将当前字母加入组合字符串，递归调用下一层for letter in phoneMap[digit]:combination.append(letter)backtrack(index + 1)# pop()函数用于移除列表中的一个元素(默认最后一个元素)，并且返回该元素的值combination.pop()  # 当combinations里面存有adg，紧接着执行for letter in phoneMap[digit]:其中digit=4combination = list()  # 初始化组合列表和当前组合字符串combinations = list()backtrack(0)  # 初始调用回溯函数return combinationsif __name__ == "__main__":# 创建 Solution 对象solution = Solution()# 调用 letterCombinations 函数并输出结果combinations = solution.letterCombinations("234")print(combinations)
class Solution:def letterCombinations(self, digits):# 如果输入为空，则直接返回空列表if not digits:return list()# 定义电话号码到字母的映射关系phoneMap = {"2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": "pqrs","8": "tuv","9": "wxyz",}def backtrack(index):# 当前组合字符串长度等于输入数字串长度时，将其加入结果集if index == len(digits):combinations.append("".join(combination))  # 获取当前数字对应的字母集合else:digit = digits[index]  # 将当前字母加入组合字符串，递归调用下一层for letter in phoneMap[digit]:combination.append(letter)backtrack(index + 1)# pop()函数用于移除列表中的一个元素(默认最后一个元素)，并且返回该元素的值combination.pop()  # 当combinations里面存有adg，紧接着执行for letter in phoneMap[digit]:其中digit=4combination = list()  # 初始化组合列表和当前组合字符串combinations = list()backtrack(0)  # 初始调用回溯函数return combinationsif __name__ == "__main__":# 创建 Solution 对象solution = Solution()# 调用 letterCombinations 函数并输出结果combinations = solution.letterCombinations("234")print(combinations)

c++完整代码：

#include<iostream>
#include<vector>
#include<unordered_map>using namespace std;class Solution{
public:vector<string> letterCombination(string digits){unordered_map<char, string> phoneMap = { // 定义数字对应的字母映射关系{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};// 处理特殊情况，如果输入为空字符串，则直接返回空列表if(digits.empty()){return vector<string> ();}// 用于存储最终的字母组合结果vector<string> result;// 回溯函数，参数分别为当前数字索引和当前已形成的组合字符串backtrack(digits,0,"",phoneMap,result);  //可以试试index等于1是什么结果，就能明白该参数具体指的是什么return result;}
private:// index ---> 数字所对应字母的索引void backtrack(const string& digits, int index, const string& path,const unordered_map<char, string>& phoneMap, vector<string>& result){// 如果当前组合字符串的长度等于输入数字串的长度，将其加入结果集if(index == digits.length()){result.push_back(path);return;}// 获取当前数字对应的字母集合char currentDigit = digits[index];const string& letters = phoneMap.at(currentDigit);// 遍历当前数字对应的字母集合，进行递归回溯for(char letter : letters){// 将当前字母加入组合字符串，递归调用下一层backtrack(digits, index + 1, path + letter, phoneMap, result);}}
};int main(){// 创建 Solution 对象Solution solution;// 调用 letterCombinations 函数并输出结果vector<string> combinations = solution.letterCombination("234");for(const string& combination : combinations){cout << combination << "" << endl;}return 0;
}

java完整代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class letterCombinations_1 {public List<String> letterCombinations(String digits) {Map<Character, String> phoneMap = new HashMap<>(); // 定义数字对应的字母映射关系phoneMap.put('2', "abc");phoneMap.put('3', "def");phoneMap.put('4', "ghi");phoneMap.put('5', "jkl");phoneMap.put('6', "mno");phoneMap.put('7', "pqrs");phoneMap.put('8', "tuv");phoneMap.put('9', "wxyz");// 处理特殊情况，如果输入为空字符串，则直接返回空列表if (digits == null || digits.isEmpty()) {return new ArrayList<>();}// 用于存储最终的字母组合结果List<String> result = new ArrayList<>();// 回溯函数，参数分别为当前数字索引和当前已形成的组合字符串backtrack(digits, 0, "", phoneMap, result);return result;}private void backtrack(String digits, int index, String path,Map<Character, String> phoneMap, List<String> result) {// 如果当前组合字符串的长度等于输入数字串的长度，将其加入结果集if (index == digits.length()) {result.add(path);return;}// 获取当前数字对应的字母集合char currentDigit = digits.charAt(index);String letters = phoneMap.get(currentDigit);// 遍历当前数字对应的字母集合，进行递归回溯for (char letter : letters.toCharArray()) {// 将当前字母加入组合字符串，递归调用下一层backtrack(digits, index + 1, path + letter, phoneMap, result);}}public static void main(String[] args) {// 创建 Solution 对象letterCombinations_1 solution = new letterCombinations_1();// 调用 letterCombinations 函数并输出结果List<String> combinations = solution.letterCombinations("234");for (String combination : combinations) {System.out.println(combination);}}
}

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

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

相关文章

opencv-4.8.0编译及使用

opencv-4.8.0编译及使用

1 编译 opencv的编译总体来说比较简单&#xff0c;但必须记住一点&#xff1a;opencv的版本必须和opencv_contrib的版本保持一致。例如opencv使用4.8.0&#xff0c;opencv_contrib也必须使用4.8.0。 进入opencv和opencv_contrib的github页面后&#xff0c;默认看到的是git分支&…
阅读更多...
浅析三种Anaconda虚拟环境创建方式和第三方包的安装

浅析三种Anaconda虚拟环境创建方式和第三方包的安装

目录 引言 一、Anaconda虚拟环境创建方式 1. 使用conda命令创建虚拟环境 2. 使用conda-forge创建虚拟环境 3. 使用Miniconda创建虚拟环境 二、第三方包的安装和管理 1. 使用 pip 安装包&#xff1a; 2. 使用 conda 安装包&#xff1a; 三、结论与建议 引言 在当今的数…
阅读更多...
【现代密码学】笔记3.1-3.3 --规约证明、伪随机性《introduction to modern cryphtography》

【现代密码学】笔记3.1-3.3 --规约证明、伪随机性《introduction to modern cryphtography》

【现代密码学】笔记3.1-3.3 --规约证明、伪随机性《introduction to modern cryphtography》 写在最前面私钥加密与伪随机性 第一部分密码学的计算方法论计算安全加密的定义&#xff1a;对称加密算法 伪随机性伪随机生成器&#xff08;PRG&#xff09; 规约法规约证明 构造安全…
阅读更多...
Nacos和Eureka比较、统一配置管理、Nacos热更新、多环境配置共享、Nacos集群搭建步骤

Nacos和Eureka比较、统一配置管理、Nacos热更新、多环境配置共享、Nacos集群搭建步骤

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、Nacos和eureka的对比二、统一配置管理二、Nacos热更新方式一方式二 三、多环境配置共享四、Nacos集群搭建步骤&#xff08;黑马springCloud的p29&#xff0…
阅读更多...
深度学习笔记（五）——网络优化（1）：学习率自调整、激活函数、损失函数、正则化

深度学习笔记（五）——网络优化（1）：学习率自调整、激活函数、损失函数、正则化

文中程序以Tensorflow-2.6.0为例 部分概念包含笔者个人理解&#xff0c;如有遗漏或错误&#xff0c;欢迎评论或私信指正。 截图和程序部分引用自北京大学机器学习公开课 通过学习已经掌握了主要的基础函数之后具备了搭建一个网络并使其正常运行的能力&#xff0c;那下一步我们还…
阅读更多...
JavaScript基础(26)_dom增删改练习

JavaScript基础(26)_dom增删改练习

<!DOCTYPE html> <html lang"zh"><head><meta charset"UTF-8"><title>DOM增删改练习</title><link rel"stylesheet" href"../browser_default_style/reset.css"><style>table {borde…
阅读更多...
vue路由及参数router

vue路由及参数router

目录 vue项目版本1、创建一个vue项目步骤 &#xff08;windows环境下&#xff09;。创建vue项目前&#xff0c;检查系统是否具备创建项目的条件&#xff08;是否已经安装好了node.js、webpack、vue-cli&#xff09;。cmd打开终端。2、vue路由vue-router解说2.1 路由视图<rou…
阅读更多...
【GDAL】Windows下VS+GDAL开发环境搭建

【GDAL】Windows下VS+GDAL开发环境搭建

Step.0 环境说明&#xff08;vs版本&#xff0c;CMake版本&#xff09; 本地的IDE环境是vs2022&#xff0c;安装的CMake版本是3.25.1。 Step.1 下载GDAL和依赖的组件 编译gdal之前需要安装gdal依赖的组件&#xff0c;gdal所依赖的组件可以在官网文档找到&#xff0c;可以根据…
阅读更多...
Kafka（七）可靠性

Kafka（七）可靠性

目录 1 可靠的数据传递1.1 Kafka的可靠性保证1.2 复制1.3 Broker配置1.3.1 复制系数1.3.2 broker的位置分布1.3.3 不彻底的首领选举1.3.4 最少同步副本1.3.5 保持副本同步1.3.6 持久化到磁盘flush.messages9223372036854775807flush.ms9223372036854775807 1.2 在可靠的系统中使…
阅读更多...
Netty开篇——基础介绍与准备（一）

Netty开篇——基础介绍与准备（一）

I/O篇 Netty的介绍 Netty 是由JBOSS提供的一个Java开源框架在Github上Netty 是一个异步的、基于事件驱动的网络应用框架&#xff0c;用以快速开发高性能、高可靠性的网络IO程序。Netty 主要针对在TCP协议下面向客户端的高并发应用&#xff0c;或者Peer-to-Peer/P2P场景下的大量…
阅读更多...
day17 平衡二叉树 二叉树的所有路径 左叶子之和

day17 平衡二叉树 二叉树的所有路径 左叶子之和

题目1&#xff1a;110 平衡二叉树 题目链接&#xff1a;110 平衡二叉树 题意 判断二叉树是否为平衡二叉树&#xff08;每个节点的左右两个子树的高度差绝对值不超过1&#xff09; 递归遍历 递归三部曲 1&#xff09;确定递归函数的参数和返回值 2&#xff09;确定终止条…
阅读更多...
数据结构链表完整实现（负完整代码）

数据结构链表完整实现（负完整代码）

文章目录 前言引入1、链表定义及结构链表的分类3、单向不带头链表实现实现完整代码 4、带头双向循环链表实现实现完整代码 前言 引入 在上一篇文章中&#xff0c;我们认识了顺序表&#xff0c;但是在许多情况中&#xff0c;顺序表在处理一些事件时还存在许多问题&#xff0c;比…
阅读更多...
鸿鹄电子招投标系统：企业战略布局下的采购寻源解决方案

鸿鹄电子招投标系统：企业战略布局下的采购寻源解决方案

在数字化采购领域&#xff0c;企业需要一个高效、透明和规范的管理系统。通过采用Spring Cloud、Spring Boot2、Mybatis等先进技术&#xff0c;我们打造了全过程数字化采购管理平台。该平台具备内外协同的能力&#xff0c;通过待办消息、招标公告、中标公告和信息发布等功能模块…
阅读更多...
数据分析——快递电商

数据分析——快递电商

一、任务目标 1、任务 总体目的——对账 本项目解决同时使用多个快递发货&#xff0c;部分隔离区域出现不同程度涨价等情形下&#xff0c;如何快速准确核对账单的问题。 1、在订单表中新增一列【运费差异核对】来表示订单运费实际有多少差异&#xff0c;结果为数值。 2、将…
阅读更多...
【无标题】关于异常处理容易犯的错

【无标题】关于异常处理容易犯的错

一般项目是方法打上 try…catch…捕获所有异常记录日志&#xff0c;有些会使用 AOP 来进行类似的“统一异常处理”。 其实&#xff0c;这种处理异常的方式非常不可取。那么今天&#xff0c;我就和你分享下不可取的原因、与异常处理相关的坑和最佳实践。 捕获和处理异常容易犯…
阅读更多...
Feature Fusion for Online Mutual KD

Feature Fusion for Online Mutual KD

paper&#xff1a;Feature Fusion for Online Mutual Knowledge Distillation official implementation&#xff1a;https://github.com/Jangho-Kim/FFL-pytorch 本文的创新点 本文提出了一个名为特征融合学习&#xff08;Feature Fusion Learning, FFL&#xff09;的框架&…
阅读更多...
行走在深度学习的幻觉中：问题缘由与解决方案

行走在深度学习的幻觉中：问题缘由与解决方案

如何解决大模型的「幻觉」问题&#xff1f; 我们在使用深度学习大模型如LLM&#xff08;Large Language Models&#xff09;时&#xff0c;可能会遇到一种被称为“幻觉”的现象。没错&#xff0c;它并不是人脑中的错觉&#xff0c;而是模型对特定模式的过度依赖&#xff0c;这…
阅读更多...
Linux---gcc编译

Linux---gcc编译

目录 前言 一、gcc编译 二、程序的编译过程 三、gcc查看编译过程 1.预处理阶段 2.编译 3.汇编 4.链接 动静态库链接的内容 动静态库链接的优缺点 5.总结记忆 前言 在前面我们学会使用vim对文件进行编辑&#xff0c;如果是C或者C程序&#xff0c;我们编辑好了内容…
阅读更多...
【DDR】基于Verilog的DDR控制器的简单实现（一）——初始化

【DDR】基于Verilog的DDR控制器的简单实现（一）——初始化

在FPGA中&#xff0c;大规模数据的存储常常会用到DDR。为了方便用户使用&#xff0c;Xilinx提供了DDR MIG IP核&#xff0c;用户能够通过AXI接口进行DDR的读写访问&#xff0c;然而MIG内部自动实现了许多环节&#xff0c;不利于用户深入理解DDR的底层逻辑。 本文以美光(Micro…
阅读更多...
【算法刷题】Day28

【算法刷题】Day28

文章目录 1. 买卖股票的最佳时机 III题干&#xff1a;算法原理&#xff1a;1. 状态表示&#xff1a;2. 状态转移方程3. 初始化4. 填表顺序5. 返回值 代码&#xff1a; 2. Z 字形变换题干&#xff1a;算法原理&#xff1a;1. 模拟2. 找规律 代码&#xff1a; 1. 买卖股票的最佳时…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023