今日题目
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = "" 输出:[]
示例 3:
输入:digits = "2" 输出:["a","b","c"]
提示:
0 <= digits.length <= 4 digits[i] 是范围 ['2', '9'] 的一个数字。
思路
从示例上来说,输入"23",最直接的想法就是两层for循环遍历了,正好把组合的情况都输出了。
如果输入"234"呢,那么就三层for循环,如果"2345"呢,就四层for循环.......
所以这种暴力破解办法的算法复杂度是至少是O(3^len(digist)),所以要想别的方案
仔细观察题目,要完成这道题需要解决如下三个问题:
- 数字和字母如何映射
- 两个字母就两个for循环,三个字符我就三个for循环,以此类推,然后发现代码根本写不出来
- 输入1 * #按键等等异常情况
对于这三个问题,相应的处理方式:
- 只要是映射关系直接考虑map,这道题key是数字且连续的,所以同时可以用数组索引当做key
- 这种情况可以利用回溯思想解决,回溯思想其实还是需要利用递归方程才能实现,把满足条件的场景存起来,然后回退,直到遍历完所有场景
- 把主要的异常场景都要考虑到,不然算法题还是很难AC,可能需要多次调试
从上面分析可以看出最难点就是在回溯思想的实现:
- 确定回溯函数参数
- 确定终止条件
- 确定单层遍历逻辑
解决方式:
- 用StringBuilder存储一次遍历的结果
- 什么时候算是一遍呢?其实是长度为输入数字的个数
- 单层循环逻辑即为,单个数字对应的字符循环
对应实现
public class Solution { // 数字到号码的映射 private final String[] map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 路径 private final StringBuilder path = new StringBuilder(); public List<String> letterCombinations(String digits) { if (digits == null || "".equals(digits)) { return Collections.emptyList(); } List<String> result = new ArrayList<>(); backtrack(result, digits, 0); return result; } // 回溯函数 private void backtrack(List<String> result, String digits, int index) { if (path.length() == digits.length()) { result.add(path.toString()); return; } String val = map[digits.charAt(index) - '2']; for (char c : val.toCharArray()) { path.append(c); backtrack(result, digits, index + 1); path.deleteCharAt(path.length() - 1); } }
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:37.2 MB, 在所有 Java 提交中击败了37.71%的用户
小结
回溯算法还是还好用的,除了占用内存比较大外,可能还有更好的解题方式,以后再分享吧,我们下道题见
今天多学一点。明天就少说一句求人的话