1.电话号码的字母组合 (17-中)
题目描述：给定一个电话号码，输入包含2-9的字符串，返回它能表示字母组合。
image.png
示例：
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
思路：本题类似全排列，且结果中不允许重复元素。
大致思路：首先根据输入索引依次找到数字，再映射到按键元素，遍历全排列。这里注意：使用StringBuilder进行结果拼接，即路径。撤销选择使用deleteCharAt（）。
代码：
//映射关系(映射键盘上0-9对应的字母)
private String[] map = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> res = new ArrayList<>();
private StringBuilder sb = new StringBuilder(); // 路径
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) return res;
backTrack(digits, 0);
return res;
}
// digits:包含数字的字符串，index:每个字符索引位置（选择列表）
private void backTrack(String digits, int index) {
if (sb.length() == digits.length()) {
res.add(sb.toString());
return;
}
// 先根据输入数字映射到按键，遍历按键元素！
String str = map[digits.charAt(index) - '0'];
for (char ch : str.toCharArray()) {
sb.append(ch);
backTrack(digits, index + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
2.复原ip地址（93-中）
题目描述：将包含数字的字符串转换成可能的ip地址。
ps：有效的ip地址：1.范围0~255；2.不能有0做前缀；3.用 . 进行分隔
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例 ：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
输入：s = "0000"
输出：["0.0.0.0"]
思路：本题与电话号码较为类似，即不同的数字组合方式，需要根据限制条件进行剪枝操作：
-
.之间的位数限制（<= 3） - 0不能作为前缀
- 数值大小限制（<= 255）
终止条件：恰好分成四组合法数字且遍历完，记录结果。否则直接返回
注意：这里的回溯是按照一块一块part进行回溯，我们得到一个块，如果满足0~255要求，我们将它添加到stringbuilder的路径里，进递归，撤销的是一块ip地址（delete函数里边设置删除起止索引），即part。
代码：
private List<String> res = new ArrayList<>();
private StringBuilder sb = new StringBuilder(); //路径
public List<String> restoreIpAddresses(String s) {
// if (s.length() < 4 || s.length() > 12) return res;
backTrack(s, 0);
return res;
}
private void backTrack(String s, int index) {
if (index == 4 || s.length() == 0) {
if (index == 4 && s.length() == 0) {
res.add(sb.toString());
}
return;
}
for (int i = 0; i < s.length() && i < 3; i++) { // 位数限制
if (i != 0 && s.charAt(0) == '0') { // 出现第一位为0，不符合规定
break;
}
String part = s.substring(0, i + 1);
if (Integer.valueOf(part) <= 255) { // 大小限制
if (sb.length() != 0) {
part = "." + part;
}
sb.append(part);
backTrack(s.substring(i + 1), index + 1);
//撤销选择
sb.delete(sb.length() - part.length(), sb.length());
}
}
}
3.在矩阵中寻找字符串（单词搜索）（79-中）
题目描述：给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
示例：
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
思路：本题可以使用递归，对四个方向进行搜索（注意一定要进行恢复！），定义index遍历单词比较。
递归遍历的终止条件：
- 遍历二维矩阵时指针越界，return false
- 当前元素被标记过，return false
- 递归过程中，只要有一个方向存在目标字母，return true
- 当前遍历到最后一个字符，搜索完毕，return true
ps：基本字符一共128个，这里标记使用异或标记，也可以使用visited数组。
代码：
public boolean exist(char[][] board, String word) {
int row = board.length, col = board[0].length;
if (board == null || row == 0 || row == 0) return false;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (existRecur(board, word, i, j, 0)) return true;
}
}
return false;
}
private boolean existRecur(char[][] board, String word, int i, int j, int index) {
if (i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1) return false;
if (board[i][j] != word.charAt(index)) return false;
if (index == word.length() - 1) return true;
// 标记当前位置
board[i][j] ^= 128;
boolean up = existRecur(board, word, i - 1, j, index + 1);
boolean down = existRecur(board, word, i + 1, j, index + 1);
boolean left = existRecur(board, word, i, j - 1, index + 1);
boolean right = existRecur(board, word, i, j + 1, index + 1);
if (up || down || left || right) return true;
// 恢复当前位置（改为未标记）
board[i][j] ^= 128;
return false;
}
4.剑指 Offer 38. 字符串的排列
思路：对于字符串的回溯，进行拼接
方案1：可以使用排序+used数组进行拼接，注意对于同一目标位置的回溯特性use[i - 1]进行剪枝
方案2：先交换元素，当交换到最后一个元素进行统一拼接
代码：
class Solution {
// 方案1：排序+used数组
private int N = 10;
private List<String> list = new ArrayList<>();
private boolean[] used = new boolean[N];
public String[] permutation(String s) {
char[] chs = s.toCharArray();
Arrays.sort(chs);
backTrack(chs, 0, "");
// String[] ans = new String[list.size()];
// int index = 0;
// for (String ss : list) {
// ans[index++] = ss;
// }
// return ans;
return list.toArray(new String[list.size()]);
}
private void backTrack(char[] chs, int level, String cur) {
if (level == chs.length) {
list.add(cur);
return;
}
for (int i = 0; i < chs.length; ++i) {
if (i > 0 && chs[i] == chs[i - 1] && !used[i - 1]) {
continue;
}
if (!used[i]) {
used[i] = true;
backTrack(chs, level + 1, cur + String.valueOf(chs[i]));
used[i] = false;
}
}
}
// 方案2：交换元素
private List<String> ans = new ArrayList<>();
public String[] permutation(String s) {
char[] chs = s.toCharArray();
Arrays.sort(chs);
backTrack(chs, 0);
return ans.toArray(new String[ans.size()]);
}
private void backTrack(char[] chs, int start) {
if (start == chs.length) {
StringBuilder sb = new StringBuilder();
for (char c : chs) {
sb.append(c);
}
ans.add(sb.toString());
return;
}
Set<Character> set = new HashSet<>();
for (int i = start; i < chs.length; ++i) {
if (set.contains(chs[i])) {
continue;
}
set.add(chs[i]);
swap(chs, i, start);
backTrack(chs, start + 1);
swap(chs, i, start);
}
}
private void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
}
5. 括号生成（T22）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
思路：本题本题不需要回溯，因为每次都使用新的字符，即我们一共有2n个字符，怎么去拼接，才能符合要求，关键点：
- 当左右扩号都用完，直接加入结果（区分T46,39），不需要再加入一个新的集合中
- 递归过程中当左括号剩余量大于右括号，拼接后的结果一定不符合。
- 递归的加入剩余的左右括号
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
if (n == 0) return ans;
dfs("", n, n, ans);
return ans;
}
public void dfs(String curStr, int left, int right, List<String> ans) {
if (left == 0 && right == 0) {
ans.add(curStr);
return;
}
if (left > right) {
return;
}
if (left > 0) {
dfs(curStr + "(", left - 1, right, ans);
}
if (right > 0) {
dfs(curStr + ")", left, right - 1, ans);
}
}
}
6. 累加数（T306）
累加数是一个字符串，组成它的数字可以形成累加序列。一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
进阶：如何处理溢出过大的整数输入？
示例：
输入: "199100199"
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
思路：直接回溯，注意剪枝条件：
- 当前数字不符合要求（写一个函数获取指定区间的有效数字）
- 当前位置不符合累加序列规则
代码：
class Solution {
public boolean isAdditiveNumber(String num) {
return dfs(num, 0, 0, 0, 0);
}
/**
* @param num 原始字符串
* @param start 当前处理下标
* @param sum 前面的两个数字之和
* @param pre 前一个数字
* @param k 当前是处理的第几个数字
*/
private boolean dfs(String num, int start, int k, long pre, long sum) {
if (start == num.length()) {
return k > 2;
}
for (int i = start; i < num.length(); ++i) {
long cur = curValue(num, start, i);
// 剪枝：存在前缀0/不满足累加序列
if (cur < 0 || k >= 2 && sum != cur) {
continue;
}
if (dfs(num, i + 1, k + 1, cur, pre + cur)) {
return true;
}
}
return false;
}
// 获取l ~ r的有效数字
private long curValue(String num, int l, int r) {
if (l < r && num.charAt(l) == '0') {
return -1;
}
long ans = 0;
while (l <= r) {
ans = ans * 10 + num.charAt(l++) - '0';
}
return ans;
}
}
7. 将数组拆分成斐波那契序列（T842）
待补充。。。
8.输出二叉树从根到叶子的所有路径(257-易)
题目描述：给定一个二叉树，返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。
示例：
输入：
1
/ \
2 3
\
5
输出： ["1->2->5", "1->3"]
思路：推荐代码1，套用模板，找到已经遍历点和未加入路径的点；代码2虽然好理解，但子树出现太多重复计算。
法1：sb变量（可变字符串序列）递归拼接已经遍历的路径。递归的终止条件是到达叶子节点，即把路径加入加入结果集，
法2：递归，假设已经知道左右子树的所有路径，最后用根节点进行连接，得到全部路径。
代码1：
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<>();
if (root == null) return ans;
backTrack(root, "", ans);
return ans;
}
// path代表该路径中已经加入的节点连接
private void backTrack(TreeNode root, String path, List<String> ans) {
if (root != null) {
StringBuilder sb = new StringBuilder(path);
sb.append(Integer.toString(root.val));
if (root.left == null && root.right == null) {
ans.add(sb.toString());
return;
} else {
sb.append("->"); // 没有到达叶子节点
backTrack(root.left, sb.toString(), ans);
backTrack(root.right, sb.toString(), ans);
}
}
}
代码2：
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<>();
if (root == null) {
return ans; //递归出口
}
//到达叶子节点,存储路径
if (root.left == null && root.right == null) {
ans.add(root.val + "");
return ans;
}
//连接左子树所有路径
for (String path : binaryTreePaths(root.left)) {
ans.add(root.val + "->" + path);
}
//连接右子树所有路径
for (String path : binaryTreePaths(root.right)) {
ans.add(root.val + "->" + path);
}
return ans;
}
总结
上述四个题目都是递归回溯的一些典型应用，需要注意一下几点：
- 这里结果表示大都用到字符串拼接，StringBuilder特点是速度快，但线程不安全，StringBuffer则恰恰相反。
- 注意建立映射关系，如T17电话号码
- 注意字符串索引切分比较
charAt()，如T93 ip地址、T79寻找字符串 - 通过递归函数找到
basecase，递归终止条件很重要，限制条件要清晰！
