回溯---电话号码的字母组合 Posted on 2021-06-29 00:00:00 2021-06-29 00:00:00 by Author 摘要 各位彦祖与亦菲，大家肯定平常都玩手机，那么你知道在平常打字聊天的过程中，会存在哪个好玩的算法思想尼，一起进来看看吧！！！！ # 回溯---电话号码的字母组合 1. 题目描述 - 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。  2. 示例描述 - 示例一 - 输入：digits = "23" - 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] - 示例二 - 输入：digits = "" - 输出：[] - 示例三 - 输入：digits = "2" - 输出：["a","b","c"] 3. 解题思路 - 本题又是一道经典的回溯与递归的算法，看起来是有点难度，但是仔细分析一下，难度点在哪里尼，个人觉得就是在递归回溯的时候，循环的集合有点难找。因为这个循环集合的条件给的不够清楚，需要我们自己去构造循环条件。 - 首先这里我们明白给定的是一个字符串，字符串每一个字符对应的就是手机中的一个键，每个键对应一串字符。所以首先就是要构造每个键对应的字符串。这里我们用Hash类型的数据结果去构造这个集合。hash表中的键为字符型，对应手机中的键，hash表中的值为字符串类型，代表手机中每个键对应的一串字符。 - 其次就是按照我自己总结的递归回溯五步法去实现具体的逻辑。首先第一步确定递归回溯的出口，如果在递归回溯过程中，当前所指向digits下标的index指针超过了digits的长度，那说明本次递归结束，还有如果临时结果字符串的长度等于digits的长度，那就说明找到一组满足条件的字符串，加入最终结果集合中。第二步就是确定递归与回溯本层要循环的集合了。本题中 没有明确说明，但是我们通过自己分析与理解，可知道本次循环的集合就是对应本次这个键所对应的字符串的序列集合。这个应该怎么得到尼，这个非常容易拿到，首先我们知道本次递归有一个遍历是指向digit的下标的遍历，我们通过这个可以得到手机中的键，再通过hasp表可以得到该键对应的字符串序列。这样就确定本次循环的集合了。第三步就是记录本次递归的值。这个根据实际情况做不同的逻辑处理，本题只需要得到字符序列的一共字符。那么我们就做相应的处理逻辑就可以了。第四步就是继续执行递归，及就是寻找本层下面的其余键的集合了。第五步就是回溯，因为递归过程中会有回退的步骤，所以当回退到本层的时候，为了不影响集合中其他字符的操作，本次操作的需要回退本次递归时的原始状态，从而不影响下次操作。 - 下面就是具体的逻辑实现，给位彦祖和亦菲可以看着代码自己再细细的品味，同时自己也可以总结自己的套路，那么以后遇到这种题目的时候，可以试试套用自己的套路去解决。 4. 代码示例 ```java //最终结果的集合 List<String> result = new ArrayList<>(); //定义一个hashMap的数据结构，为了存储手机键中的键值对 Map<Character,String> keyBoard = new HashMap<>(); //初始化hashMap表 public void initKeyBoard(){ keyBoard.put('2',"abc"); keyBoard.put('3',"def"); keyBoard.put('4',"ghi"); keyBoard.put('5',"jkl"); keyBoard.put('6',"mno"); keyBoard.put('7',"pqrs"); keyBoard.put('8',"tuv"); keyBoard.put('9',"wxyz");; } public List<String> letterCombinations(String digits) { //如果所给的一串数组字符串为空，直接返回 if(digits.length()<=0){ return result; } //首先初始化HashMap表 initKeyBoard(); //调用自己写的递归回溯算法，找到找到最终结果 trackBack(digits,0,""); return result; } public void trackBack(String digits,int index,String tempResult){ //递归出口，如果临时结果的长度与所给数字字符串的长度相等，说明找到一组集合 if(tempResult.length()==digits.length()){ result.add(tempResult); return; } //如果指向数字字符串下标的值超过了该字符串的长度，说明没必要继续下面的操作。 //此时已经结束本次递归了 if(index>=digits.length())return; //下面两行代码就是找出本次递归时循环的集合 //第一步找出本次选择手机中的哪个键 char c = digits.charAt(index); //第二步就是得到改键对应的字符串序列 char[] number_to_chars = keyBoard.get(c).toCharArray(); //继续循环递归，找出本层所有满足条件的结果 for (int i = 0; i < number_to_chars.length; i++) { //记录本次递归的值 tempResult+=number_to_chars[i]; //继续执行本层的下层递归。 trackBack(digits,index+1,tempResult); //移除本次递归的值，以便集合中其他字符能够正常操作 tempResult = tempResult.substring(0,tempResult.length()-1); } } ```
{{ item.content }}
{{ child.content }}