【算法攻坚】回溯电话号码

发表于

这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战

今日题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 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存储一次遍历的结果
  • 什么时候算是一遍呢？其实是长度为输入数字的个数
  • 单层循环逻辑即为，单个数字对应的字符循环

对应实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
java复制代码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%的用户

小结

回溯算法还是还好用的，除了占用内存比较大外，可能还有更好的解题方式，以后再分享吧，我们下道题见

今天多学一点。明天就少说一句求人的话

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%