LeetCode 回溯专题 2：回溯法是暴力解法的一个主要的实现
2019-05-28 本文已影响0人
李威威
回溯法要发现递归结构，本质上是暴力解法。这一节的开始，我们先对上一节的代码的执行流程进行分析，我们首先给程序添加一些打印的语句，这样我们就能清晰地观察函数的执行流程。
在递首先我们在递归方法中添加一些打印输出语句，以便观察代码的执行顺序。
LeetCode 第 17 题 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()) {
System.out.println("已经从根节点走到叶子节点，得到的一个组合是：" + pre);
System.out.println();
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++) {
System.out.println("当前的索引是：" + index + "，已经得到的字符串是：" + pre);
findCombination(digits, index + 1, pre + currentStr.charAt(i));
}
System.out.println("当前的索引是：" + index + "，已经得到的字符串是：" + pre);
}
}
以 "234" 作为测试用例，运行代码，对比上面画出的图观察输出语句：
当前的索引是：0，已经得到的字符串是：
当前的索引是：1，已经得到的字符串是：a
当前的索引是：2，已经得到的字符串是：ad
已经从根节点走到叶子节点，得到的一个组合是：adg
当前的索引是：2，已经得到的字符串是：ad
已经从根节点走到叶子节点，得到的一个组合是：adh
当前的索引是：2，已经得到的字符串是：ad
已经从根节点走到叶子节点，得到的一个组合是：adi
当前的索引是：2，已经得到的字符串是：ad
当前的索引是：1，已经得到的字符串是：a
当前的索引是：2，已经得到的字符串是：ae
已经从根节点走到叶子节点，得到的一个组合是：aeg
当前的索引是：2，已经得到的字符串是：ae
已经从根节点走到叶子节点，得到的一个组合是：aeh
当前的索引是：2，已经得到的字符串是：ae
已经从根节点走到叶子节点，得到的一个组合是：aei
当前的索引是：2，已经得到的字符串是：ae
当前的索引是：1，已经得到的字符串是：a
当前的索引是：2，已经得到的字符串是：af
已经从根节点走到叶子节点，得到的一个组合是：afg
当前的索引是：2，已经得到的字符串是：af
已经从根节点走到叶子节点，得到的一个组合是：afh
当前的索引是：2，已经得到的字符串是：af
已经从根节点走到叶子节点，得到的一个组合是：afi
当前的索引是：2，已经得到的字符串是：af
当前的索引是：1，已经得到的字符串是：a
当前的索引是：0，已经得到的字符串是：
当前的索引是：1，已经得到的字符串是：b
当前的索引是：2，已经得到的字符串是：bd
已经从根节点走到叶子节点，得到的一个组合是：bdg
当前的索引是：2，已经得到的字符串是：bd
已经从根节点走到叶子节点，得到的一个组合是：bdh
当前的索引是：2，已经得到的字符串是：bd
已经从根节点走到叶子节点，得到的一个组合是：bdi
当前的索引是：2，已经得到的字符串是：bd
当前的索引是：1，已经得到的字符串是：b
当前的索引是：2，已经得到的字符串是：be
已经从根节点走到叶子节点，得到的一个组合是：beg
当前的索引是：2，已经得到的字符串是：be
已经从根节点走到叶子节点，得到的一个组合是：beh
当前的索引是：2，已经得到的字符串是：be
已经从根节点走到叶子节点，得到的一个组合是：bei
当前的索引是：2，已经得到的字符串是：be
当前的索引是：1，已经得到的字符串是：b
当前的索引是：2，已经得到的字符串是：bf
已经从根节点走到叶子节点，得到的一个组合是：bfg
当前的索引是：2，已经得到的字符串是：bf
已经从根节点走到叶子节点，得到的一个组合是：bfh
当前的索引是：2，已经得到的字符串是：bf
已经从根节点走到叶子节点，得到的一个组合是：bfi
当前的索引是：2，已经得到的字符串是：bf
当前的索引是：1，已经得到的字符串是：b
当前的索引是：0，已经得到的字符串是：
当前的索引是：1，已经得到的字符串是：c
当前的索引是：2，已经得到的字符串是：cd
已经从根节点走到叶子节点，得到的一个组合是：cdg
当前的索引是：2，已经得到的字符串是：cd
已经从根节点走到叶子节点，得到的一个组合是：cdh
当前的索引是：2，已经得到的字符串是：cd
已经从根节点走到叶子节点，得到的一个组合是：cdi
当前的索引是：2，已经得到的字符串是：cd
当前的索引是：1，已经得到的字符串是：c
当前的索引是：2，已经得到的字符串是：ce
已经从根节点走到叶子节点，得到的一个组合是：ceg
当前的索引是：2，已经得到的字符串是：ce
已经从根节点走到叶子节点，得到的一个组合是：ceh
当前的索引是：2，已经得到的字符串是：ce
已经从根节点走到叶子节点，得到的一个组合是：cei
当前的索引是：2，已经得到的字符串是：ce
当前的索引是：1，已经得到的字符串是：c
当前的索引是：2，已经得到的字符串是：cf
已经从根节点走到叶子节点，得到的一个组合是：cfg
当前的索引是：2，已经得到的字符串是：cf
已经从根节点走到叶子节点，得到的一个组合是：cfh
当前的索引是：2，已经得到的字符串是：cf
已经从根节点走到叶子节点，得到的一个组合是：cfi
当前的索引是：2，已经得到的字符串是：cf
当前的索引是：1，已经得到的字符串是：c
当前的索引是：0，已经得到的字符串是：
我们发现，代码从树的根走到一个分支的叶子节点以后，就会返回到叶子节点的父节点，然后再走到之前那个节点的兄弟节点，这个过程就是回溯的过程：先沿着一条路径一直走到底，走到底以后，就回头，寻找另一条能走到底的路径，是不是有点深度优先遍历的意思；
我们还可以发现，尽管形式上是递归，但是函数的执行流程是顺序执行流程，只不过，在执行的过程中，函数自己调用了自己。在自己这个函数返回以后，回到上一层函数还是自己，但是每一次调用自己的时候，参数都不尽相同。
递归调用的一个重要特征就是回溯
底层的递归方法调用结束以后，我们总是要返回到上一层（这里有系统栈的支持），继续递归调用。这个回到上一级函数调用过程就是回溯，回溯是递归调用的一个重要的特征。回溯法是暴力解法的一个主要的实现手段。这种回溯的方法，在每一层都在遍历，所以时间复杂度并不高。
既然说它是暴力解法，那么为什么我们不使用循环在解空间里面搜索呢？仔细思考一下，如果要使用循环，数字字符串里有几个数字，就要写几层循环，实在是太恐怖了，所以不能使用简单的循环遍历，于是我们可以使用回溯法来解决这个问题。
在后续的学习中，我们还会看到回溯算法在其它问题上的应用。
1、动态规划：在回溯的过程中还要满足其它的条件；
2、回溯过程中我们有的时候需要剪枝，不须要全部进行暴力，即不用走到最底（不用到达所有的叶子节点）。
练习
练习1：LeetCode 第 93 题：复原 IP 地址
传送门：英文网址：93. Restore IP Addresses ，中文网址：93. 复原IP地址 。
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
思路：使用深度优先遍历、递归回溯的思想来完成。
1、IP 地址一共 4 段，每一段的最大值是 255，最小值是 0，我们采用搜索的办法来得到有效的 ip 段；
2、每一次循环判断接下来读进来的 3 个数字字符是有可能成为一个 ip 段，如果可以，加到已经形成的 ip 段后面（特别要注意，截取字符串的时候不能越界）；
3、接下来递归终止的条件就得分析清楚了，但是也不是难事，把握好总共分 4 段，当画上第 4 个点，并且下一个考察的下标已经“刚刚好”越界的时候，此时，我们就找到了一个有效的 ip 段分割。
Java 代码：
import java.util.ArrayList;
import java.util.List;
// https://leetcode-cn.com/problems/restore-ip-addresses/description/
public class Solution {
private List<String> res = new ArrayList<>();
private boolean judgeIfIPSegment(String ipSegment) {
int len = ipSegment.length();
// 大于 1 位的时候，不能以 0 开头
if (len > 1 && ipSegment.startsWith("0")) {
return false;
}
return Integer.parseInt(ipSegment) <= 255;
}
private void findIpSegment(String s, int split, int begin, String pre) {
// 先写递归终止条件
if (split == 4) {
if (begin == s.length()) {
res.add(pre.substring(0, pre.length() - 1));
}
return;
}
// split < 4 的时候
// begin + i <= s.length() 容易被忽略
for (int i = 1; i <= 3 && begin + i <= s.length(); i++) {
// 可能成为 ip 段的字符串
String ifIpSegment = s.substring(begin, begin + i);
if (judgeIfIPSegment(ifIpSegment)) {
findIpSegment(s, split + 1, begin + i, pre + ifIpSegment + '.');
}
}
}
public List<String> restoreIpAddresses(String s) {
int len = s.length();
if (len == 0) {
return res;
}
findIpSegment(s, 0, 0, "");
return res;
}
public static void main(String[] args) {
// write your code here
String s = "25525511135";
Solution solution = new Solution();
List<String> restoreIpAddresses = solution.restoreIpAddresses(s);
System.out.println(restoreIpAddresses);
}
}
练习2：LeetCode 第 131 题：分割回文串
传送门：分割回文串。
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
Java 代码：
import java.util.ArrayList;
import java.util.List;
public class Solution {
private List<List<String>> res = new ArrayList<>();
// 判断是否回文
private boolean judgeIfReverse(String s) {
int len = s.length();
if (len == 0 || len == 1) {
return true;
}
// 01210 5 2
// 012210 6 3
for (int i = 0; i < len / 2; i++) {
if (s.charAt(i) != s.charAt(len - 1 - i)) {
return false;
}
}
return true;
}
private List<String> arrConvertList(String str) {
List<String> res = new ArrayList<>();
for (String s : str.split(",")) {
res.add(s);
}
return res;
}
private void findReverse(String s, int begin, String pre) {
if (begin == s.length()) {
res.add(arrConvertList(pre));
return;
}
for (int i = begin + 1; i <= s.length(); i++) {
String ifReserve = s.substring(begin, i);
if (judgeIfReverse(ifReserve)) {
findReverse(s, i, pre + ifReserve + ",");
}
}
}
public List<List<String>> partition(String s) {
int len = s.length();
if (len == 0) {
return res;
}
findReverse(s, 0, "");
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "aab";
List<List<String>> partition = solution.partition(s);
System.out.println(partition);
}
}
（本节完）
