东莞短视频推广方法,温州做网站整站优化,南昌做网站的公司多不多,做网页局域网站点配置电话号码的字母组合
力扣原题链接
问题描述
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。
示例
示例 1#xff1a;…电话号码的字母组合
力扣原题链接
问题描述
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例
示例 1
输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2
输入digits “” 输出[]
示例 3
输入digits “2” 输出[“a”,“b”,“c”]
解题思路
这是一个典型的回溯算法问题。我们需要根据数字到字母的映射将给定的数字字符串转换为所有可能的字母组合。
代码思路
构建数字到字母的映射表 首先构建一个数组 LETTERS用于存储数字到字母的映射数组下标代表数字数组元素代表对应的字母字符串。初始化结果列表 创建一个空的列表 combinations用于存储最终的字母组合结果。回溯搜索 定义一个回溯函数 backtrack其参数包括当前数字字符串 digits、当前处理的索引 index、当前的字母组合路径 path。结束条件 如果当前路径长度等于数字字符串的长度则将当前路径加入结果列表并返回。选择列表 获取当前数字对应的字母集合。遍历选择 遍历当前数字对应的字母集合对每个字母进行递归搜索。做出选择 将当前字母加入路径。递归进入下一层 递归调用回溯函数传入新的索引 index1继续搜索下一个数字对应的字母。撤销选择 回溯到上一层时将当前选择的字母从路径中删除继续遍历下一个字母。 Java解题
垃圾版
class Solution {MapInteger, String en new HashMap(); ListString res new ArrayList();public ListString letterCombinations(String digits) {if(digits.equals()|| digits null) return res;en.put(0,);en.put(1,);en.put(2,abc);en.put(3,def);en.put(4,ghi);en.put(5,jkl);en.put(6,mno);en.put(7,pqrs);en.put(8,tuv);en.put(9,wxyz);String s new String();backtract(digits,0,s);return res;}public void backtract(String digits,int index,String s){if(index digits.length()){res.add(s);return;}String arr en.get(Integer.parseInt(String.valueOf(digits.charAt(index))));for(int i 0 ;iarr.length();i){s arr.charAt(i);backtract(digits,index1,s);s s.substring(0,s.length()-1);}}
}优化版
直接使用String 数组就行数组下标和元素就是一个二维映射不用使用hash表的计算查询。收集结果使用StringBuilder避免String进行拼接裁剪时的新建。
import java.util.*;class Solution {// 存储数字到字母的映射关系private static final String[] LETTERS {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};// 存储最终结果的列表private ListString combinations new ArrayList();public ListString letterCombinations(String digits) {if (digits.length() 0) {return combinations;}backtrack(digits, 0, new StringBuilder());return combinations;}// 回溯函数private void backtrack(String digits, int index, StringBuilder path) {// 如果路径长度等于数字字符串的长度将路径加入结果列表if (index digits.length()) {combinations.add(path.toString());return;}// 获取当前数字对应的字母集合String letters LETTERS[digits.charAt(index) - 0];// 遍历当前数字对应的字母集合for (char letter : letters.toCharArray()) {// 做出选择path.append(letter);// 递归进入下一层决策树backtrack(digits, index 1, path);// 撤销选择path.deleteCharAt(path.length() - 1);}}
}通过回溯算法我们可以找出给定数字字符串能表示的所有字母组合。
