[LeetCode] Letter conbinations of a phone number算法-递归-回溯法

柔光的暖阳◎ 2022-04-14 03:20 166阅读 0赞

## **问题:** ##

**17  Letter conbinations of a phone number**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70][]

## 测试数据: ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1][]

## 边界控制: ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2][]

## 图形化表述: ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 3][]

## 表达式表述: ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 4][]

算法:

import java.util.List;
    import java.util.ArrayList;
    
    /// 17. Letter Combinations of a Phone Number
    /// https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
    /// 时间复杂度: O(2^len(s))
    /// 空间复杂度: O(len(s))
    class Main {
        //利用数组索引实现匹配,而没有使用key-value
        private String letterMap[] = {
                " ",    //0
                "",     //1
                "abc",  //2
                "def",  //3
                "ghi",  //4
                "jkl",  //5
                "mno",  //6
                "pqrs", //7
                "tuv",  //8
                "wxyz"  //9
        };
        //全局变量,用于保存s
        private ArrayList<String> res;
         //调用主函数
        public List<String> letterCombinations(String digits) {
            //初始化
            res = new ArrayList<String>();
            //如果是空字符就返回不做处理
            if(digits.equals(""))
                return res;
            //调用递归函数,使用递归琢步向后生成相应的字符串 , index 代表索引开始位置,首先肯定是从0开始,而且生成的结果s也初始为空
            findCombination(digits, 0, "");
            return res;
        }
    
    
        // s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
        // 寻找和digits[index]匹配的字母, 获得digits[0...index]翻译得到的解
        private void findCombination(String digits, int index, String s){
    
            System.out.println(index + " : " + s);
            //索引指向了数字字符串的末尾,意味着已经遍历到底了, 此时获取到的s就是问题的一个解了,所以
            //应该把s保存起来,否则继续递归调用
            if(index == digits.length()){
                res.add(s);
                System.out.println("get " + s + " , return");
                return;
            }
            //c遍历的是数字字符串的索引对应值,如 digist=234, index =0,  c=2
            Character c = digits.charAt(index);
            assert  c.compareTo('0') >= 0 &&
                    c.compareTo('9') <= 0 &&
                    c.compareTo('1') != 0;
            //当前的数字字符对应的字母,如 2 对应了 abc
            String letters = letterMap[c - '0'];
            //对得到的字母进行遍历,如abc
            for(int i = 0 ; i < letters.length() ; i ++){
                System.out.println("digits[" + index + "] = " + c +
                        " , use " + letters.charAt(i));
                //因为已经处理了当前的数字字符串index,接下来要处理下一位的index  ,所以是index+1
                //s中保存了此时从digits[0...index-1]翻译得到的一个字母字符串
                //当遍历第二个字符时, 将第二个字符放在s的后面,从而基于一个新的字符串向下遍历
                findCombination(digits, index+1, s + letters.charAt(i));
            }
    
            System.out.println("digits[" + index + "] = " + c + " complete, return");
    
            return;
        }
    
        private static void printList(List<String> list){
            for(String s: list)
                System.out.println(s);
        }
    
        public static void main(String[] args) {
            printList((new Main()).letterCombinations("23"));
        }
    }

## 感受: ##

这里将最核心的代码贴出 :

private void findCombination(String digits, int index, String s)\{  
    if(index == digits.length())\{//递归终止条件  
        res.add(s);  
        return;  
    \}  
    String letters = letterMap\[digits.charAt(index) - '0'\];  
    for(int i = 0 ; i < letters.length() ; i ++)\{   
        findCombination(digits, index+1, s + letters.charAt(i));  
    \}  
    return;  
\}

通过比较其他递归例题和算法,发现本题特别之处在于在递归中使用了for ,   相比于斐波那契数列, 阶乘, 汗塔塔 等,原因在于有本题的算法路径有一个"回溯"情况,以左半树为例  ,流程显示:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 5][]

## 类似问题: ##

**1. restore ip addresses **

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 6][]

2.palindrome partitioning

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 7][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70]: /images/20220414/f83d8eb0e8f14c9cbb2b66b01134b6b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1]: /images/20220414/c153a8696020431faaf12fa997979efb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2]: /images/20220414/c7883aa3c4ac46c5a1dd17c24470b0aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 3]: /images/20220414/72bb9b761383437c99ba402e3c02cb42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 4]: /images/20220414/c6957a13e89d40bcb80e010e510216ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 5]: /images/20220414/0b8edb65fe0a4033a900f2b98f4e3c3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 6]: /images/20220414/8c43a44871344fbbae4719f37048d1bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 7]: /images/20220414/63d31833b8b1402c91af0c9449ac40bf.png