[Leetcode][第17题][JAVA][电话号码的字母组合][回溯]

雨点打透心脏的1/2处 2022-12-01 05:20 119阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

用哈希表/数组存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

###### 1. 回溯 哈希表 ######

class Solution { 
        public List<String> letterCombinations(String digits) { 
            List<String> combinations = new ArrayList<String>();
            if (digits.length() == 0) { 
                return combinations;
            }
            Map<Character, String> phoneMap = new HashMap<Character, String>() { { 
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
            return combinations;
        }
    
        public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) { 
            if (index == digits.length()) { 
                combinations.add(combination.toString());
            } else { 
                char digit = digits.charAt(index);
                String letters = phoneMap.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) { 
                    combination.append(letters.charAt(i));
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }
    }

###### 2. 回溯 数组存储 ######

class Solution { 
    
        // 数字到号码的映射
        private String[] map = { "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    
        // 路径
        private StringBuilder sb = new StringBuilder();
    
        // 结果集
        private List<String> res = new ArrayList<>();
    
        public List<String> letterCombinations(String digits) { 
            if(digits == null || digits.length() == 0) return res;
            backtrack(digits,0);
            return res;
        }
    
        // 回溯函数
        private void backtrack(String digits,int index) { 
            if(sb.length() == digits.length()) { 
                res.add(sb.toString());
                return;
            }
            String val = map[digits.charAt(index)-'2'];
            for(char ch:val.toCharArray()) { 
                sb.append(ch);
                backtrack(digits,index+1);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }

#### 【总结】 ####

###### 1. 回溯递归通用模板，即用一个临时数组temp 来保存当前选出的子序列，使用cur 来表示当前位置的下标，在 dfs(cur, nums) 开始之前，\[0,cur−1\] 这个区间内的所有元素都已经被考虑过，而\[cur,n\] 这个区间内的元素还未被考虑。在执行 dfs(cur, nums) 时，我们考虑 cur 这个位置选或者不选，如果选择当前元素，那么把当前元素加入到temp 中，然后递归下一个位置，在递归结束后，应当把temp 的最后一个元素删除进行回溯；如果不选当前的元素，直接递归下一个位置。 ######

List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> temp = new ArrayList<Integer>();
    public void dfs(int cur, int[] nums) { 
        if (cur == nums.length) { 
            // 判断是否合法，如果合法判断是否重复，将满足条件的加入答案
            if (isValid() && notVisited()) { 
                ans.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        // 如果选择当前元素
        temp.add(nums[cur]);
        dfs(cur + 1, nums);
        temp.remove(temp.size() - 1);
        // 如果不选择当前元素
        dfs(cur + 1, nums);
    }

###### 2.回溯相关题目 ######

[\[Leetcode\]\[第491题\]\[JAVA\]\[递增子序列\]\[回溯\]\[RK算法\]][Leetcode_491_JAVA_RK]  
[\[Leetcode\]\[第679题\]\[JAVA\]\[24点游戏\]\[回溯\]\[暴力\]  
][Leetcode_679_JAVA_24_]  
\[Leedcode\]\[JAVA\]\[第46题\]\[全排列\]\[回溯算法\]  
[\[Leetcode\]\[第93题\]\[JAVA\]\[复原IP地址\]\[剪枝\]\[回溯\]][Leetcode_93_JAVA_IP]  
[\[剑指offer\]面试题第\[38\]题\[JAVA\]\[字符串的排列\]\[回溯法\]][offer_38_JAVA]  
[\[剑指offer\]\[JAVA\]面试题第\[34\]题\[二叉树中和为某一值的路径\]\[回溯\]][offer_JAVA_34]  
[\[Leetcode\]\[第17题\]\[JAVA\]\[电话号码的字母组合\]\[回溯\]][Leetcode_17_JAVA]  
参考链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b11dd90b5cb142b19af6de9fbd3d8ccb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/23c7c75744d9479db1693f96451b6016.png
[Leetcode_491_JAVA_RK]: https://blog.csdn.net/dadongwudi/article/details/108216031
[Leetcode_679_JAVA_24_]: https://blog.csdn.net/dadongwudi/article/details/108164797
[Leetcode_93_JAVA_IP]: https://blog.csdn.net/dadongwudi/article/details/107924709
[offer_38_JAVA]: https://blog.csdn.net/dadongwudi/article/details/107037893
[offer_JAVA_34]: https://blog.csdn.net/dadongwudi/article/details/106969071
[Leetcode_17_JAVA]: https://blog.csdn.net/dadongwudi/article/details/108235943