LeetCode 回溯专题 1：在树形问题中使用递归

作者: 李威威 | 来源:发表于2019-05-28 23:18 被阅读0次

回溯法是解决很多算法问题的常见思想，甚至可以说是传统人工智能的基础方法。其本质依然是使用递归的方法在树形空间中寻找解。在这一章，我们来具体看一下将递归这种技术使用在非二叉树的结构中，从而认识回溯这一基础算法思想。

在解决二叉树的问题的中我们已经看到了递归算法的威力和有趣之处，也体会到了使用递归算法的痛点。当然，递归算法也绝不仅仅只是适用于二叉树问题的解决。从这一节开始，我们会在更多、更广义的问题上，使用递归算法。

递归算法还能够解决的一个典型问题，是具有树形结构的问题，当我们发现一个问题与一个更小的问题之间存在递归关系的时候，此时，递归关系呈现出来的就是一个树形结构。

为此，我们从一个比较简单的问题入手，介绍什么是树形问题。

例题：LeetCode 第 17 题“数字字母匹配表”

传送门：英文网址：17. Letter Combinations of a Phone Number ，中文网址：17. 电话号码的字母组合。

给出一个数字字符串，返回这个数字字符串能表示的所有字母的组合。例如：对数字字符串 “23”，返回：[“ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
LeetCode 第 17 题“数字字母匹配表”-1

例如：对数字字符串 “23”，输出：[“ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

分析：对该问题的思考：
1、字符串的合法性（能出现什么样的字符串，“@”可以吗？“1”可以吗？）；
2、空字符串（如果给出的是空字符串，返回什么）；
3、多个解的顺序（我们这个问题中对顺序没有要求）。

我的思考：这个问题更像数学问题中的乘法计数原理：

第 1 步，考虑数字 2 能表达的三个字母；

第 2 步，考虑 3 能表达的三个字母。

于是，我们最容易想到用多重循环来解决这个问题。但是在步数很多的时候，循环就变得低效了。下面，我们看看如何从递归的角度去思考该问题。这个问题其实是一个典型的树形问题。我们画出下面的图，就可以一目了然。

LeetCode 第 17 题“数字字母匹配表”-2

从图中，我们可以看出，一条从根节点到叶子节点（root-leaf）的路径，就是我们要找的组合中的一种情况。于是，我们把上面的思路更加抽象、形式化表述成如下：

设 $digits$ 是题中所述的数字字符串， $s(digits)$ 是 $digits$ 表示所能代表的字母字符串，那么有：

$\begin{equation}\begin{split} s(digits[0…n-1]) & = letter(digits[0]) + s(digits[1…n-1]) \\ & = letter(digits[0]) + letter(digits[1]) + s(digits[2…n-1]) \\ & = …… \end{split}\end{equation}$

注意：这个关系式一直写到底，就是 $letter(digits[0]) + letter(digits[1]) + ... + letter(digits[n-1])$ ，所以，只要计算出 $letter(digits[n-1])$ ，就可以执行相关的操作（打印输出，或者添加到一个结果集中），然后函数返回。这就是我们就发现的递归关系。

Python 代码：

class Solution:
    digits_array = [" ", "", "abc", "def", "ghi", "jkl", "mno",
                    "pqrs", "tuv", "wxyz"]

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """

        if len(digits) == 0:
            return []
        res = []

        self.__dfs(digits, 0, '', res)
        return res

    def __dfs(self, digits, index, pre, res):
        """
        :param digits: 字母表，全局
        :param index: 当前看第几个数字
        :param pre: 已经得到的字符串
        :param res: 保存最终结果
        :return:
        """
        if index == len(digits):
            # 可以结算了
            res.append(pre)
            return

        s = self.digits_array[int(digits[index])]
        for alpha in s:
            self.__dfs(digits, index + 1, pre + alpha, res)

Java 代码：

public class Solution {

    /**
     * 要弄清楚递归关系的话，只要搞清楚一句话：
     * 这个问题是一个典型的树形问题，体现的递归（recursion）过程是，
     * 之前的字符串 + 当前字符，就能得到一个新的字符串
     */
    private List<String> strList = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits == null || "".equals(digits)) {
            return strList;
        }
        findCombination(digits, 0, "");
        return strList;
    }

    /**
     * Combination 组合
     * 该函数，找到 index 索引代表的数字字符串，并且获得 digits[0,...,index] 翻译得到的字符串
     *
     * @param digits 原始的数字字符串
     * @param index 当前定位到了原数字字符串的哪个索引
     * @param pre    pre 保存了从 digits[0,...,index-1] 翻译得到的某一个字符串
     */
    private void findCombination(String digits, int index, String pre) {
        String[] digitsMap = new String[]{
                " ", // 0
                "",  // 1
                "abc", // 2
                "def", // 3
                "ghi", // 4
                "jkl", // 5
                "mno", // 6
                "pqrs", // 7
                "tuv", // 8
                "wxyz"  // 9
        };
        // 已经走到了最后一位 + 1，，即当前如果定位到了最大索引的下一个，就是取不到值的情况，函数就可以返回了
        if (index == digits.length()) {
            strList.add(pre);
            return;
        }
        char c = digits.charAt(index);
        assert c >= '0' || c <= '9' || c != '1';
        String currentStr = digitsMap[c - '0'];
        for (int i = 0; i < currentStr.length(); i++) {
            findCombination(digits, index + 1, pre + currentStr.charAt(i));
        }
    }

    // 测试用例
    public static void main(String[] args) {
        String digits = "23";
        Solution solution = new Solution();
        List<String> letters = solution.letterCombinations(digits);

        for (String s : letters) {
            System.out.println(s);
        }
    }
}

Java 代码：

/**
 * 找到 index 索引代表的数字字符串，并且获得 digits[0,...,index] 翻译得到的字符串
 *
 * @param digits 原始的数字字符串
 * @param index  当前定位到了原始数字字符串的哪个位置
 * @param pre    pre 保存了从 digits[0,...,index-1] 翻译得到的其中一个字符串
 *               这里 pre.length == index 的结果为 true
 */
private void findCombinations(String digits, int index, String pre) {
    // 0 对应空格，1 不对应任何字母，这里虽然写上了，但是只是占了一个位置
    String[] digitsMap = new String[]{" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    // 先处理递归到底的情况
    // 已经走到了最后一位 + 1，即当前如果定位到了最大索引的下一个，就是取不到值的情况，函数就可以返回了
    if (index == digits.length()) {
        // 体会这一步是很关键的
        result.add(pre);
        return;
    }
    // 当前数字所表示的字符串
    // assert c >= '0' || c <= '9' || c != '1';
    String currStr = digitsMap[digits.charAt(index) - '0'];
    for (int i = 0; i < currStr.length(); i++) {
        findCombinations(digits, index + 1, pre + currStr.charAt(i));
    }
}

总结：

1、为什么我们要再写一个函数，而不是直接在原来的 letterCombinations 函数中书写呢？这是因为，我们发现的递归关系并不能用 letterCombinations 函数来描述，也就是递归过程把问题转化成为一个规模更小的问题，而这个规模更小的问题，不能使用 letterCombinations() 来表述；

2、我们在使用递归方法解决问题的时候，一定不能忽略边界的情况的处理。

刷题心得（第 2 遍）

1、递归终止条件要仔细考虑，特别是对边界的情况；

2、如何设计递归方法其实是有固定模式的，参数的设定也是有规律的，无非是弄清楚之前是什么，当前是什么，然后把当前的加到之前的；

3、对于数字字符转换为数字，这里使用的是 digits.charAt(index) - '0'；

4、严格意义上说，还要对所输入的数字字符的合法性作判断，例如：assert c >= '0' || c <= '9' || c != '1';；

5、findCombination 函数中的 digitsMap 可以写成成员变量；

6、这里因为 String 是不可变对象，所以每一次的方法调用，其实都是新的对象传递下去，这一点在我们后续的练习中要留意（这句话表达比较隐晦，要深刻理解这个事实还要做后面的练习，当 result 是其它类型的对象的时候，就不能简单的 add 操作了）。

（本节完）

LeetCode 回溯专题 1：在树形问题中使用递归

例题：LeetCode 第 17 题“数字字母匹配表”

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读