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，递归终止条件很重要，限制条件要清晰！
