【LeetCode】 17. 电话号码的字母组合

水深无声 2021-06-10 20:38 369阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

毫不意外，这道题又是看了解析才会做了，这道题目也是典型的递归

注意这是回溯板块儿下的一道题目，所以这里面用到了回溯的方法，要清楚的是递归和回溯，是不同的，`递归是一种算法结构，回溯是一种算法思想`

### 代码 ###

class Solution { 
        String[] strs = new String[]{ "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> res = new ArrayList<>();
        String digits;
    
        public List<String> letterCombinations(String digits) { 
            if (digits.equals("")) return res;
            this.digits = digits;
            combination(0, "");
            return res;
        }
    	// i: 索引
    	// prefix: 每次拼接完成的字符串
        public void combination(int i, String prefix) { 
            if (i >= digits.length()) { 
                res.add(prefix);
                return;
            }
            String letters = strs[digits.charAt(i) - '2'];
            for (int j = 0; j < letters.length(); j++) { 
                combination(i + 1, prefix + letters.charAt(j));
            }
        }
    }

[Link 1]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/0a223845fd9c45978a9feb56843a9084.png