首页 > 代码库 > Chapter five Depth First Search（深度优先搜索）
Chapter five Depth First Search（深度优先搜索）
组合搜索问题 Combination
问题模型：求出所有满足条件的“组合”。判断条件：组合中的元素是顺序无关的。时间复杂度：与 2^n 相关。
1.Chapter one 第2题 subsets(子集）
2.Chapter one 第3题 subsets-ii(子集II）
3.combination-sum（数字组合）
给出一组候选数字(C)和目标数字(T),找到C中所有的组合，使找出的数字和为T。C中的数字可以无限制重复被选取。所有的数字(包括目标数字)均为正整数。元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。解集不能包含重复的组合。
例如,给出候选数组[2,3,6,7]和目标数字7，解集为：[[7],[2,2,3]]
public class Solution { /** * @param candidates: A list of integers * @param target:An integer * @return: A list of lists of integers */ public List<List<Integer>> combinationSum(int[] candidates, int target) { // write your code here List<List<Integer>> results = new ArrayList<List<Integer>>(); if (candidates == null || candidates.length == 0) { return results; } Arrays.sort(candidates); List<Integer> combination = new ArrayList<Integer>(); dfs(candidates, 0, target, combination, results); return results; } private void dfs(int[] candidates, int index, int target, List<Integer> combination, List<List<Integer>> results) { if (target == 0) { results.add(new ArrayList<Integer>(combination)); return; } for (int i = index; i < candidates.length; i++) { if (i != index && candidates[i] == candidates[i - 1]) { continue; } if (candidates[i] > target) { break; } combination.add(candidates[i]); dfs(candidates, i, target - candidates[i], combination, results); combination.remove(combination.size() - 1); } } }
4.combination-sum-ii（数字组合II）
给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。所有的数字(包括目标数字)均为正整数。元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。解集不能包含重复的组合。
例如，给出候选数字集合[10,1,6,7,2,1,5] 和目标数字 8 ,解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]
public class Solution { /** * @param num: Given the candidate numbers * @param target: Given the target number * @return: All the combinations that sum to target */ public List<List<Integer>> combinationSum2(int[] num, int target) { // write your code here List<List<Integer>> results = new ArrayList<List<Integer>>(); if (num == null || num.length == 0) { return results; } Arrays.sort(num); List<Integer> combination = new ArrayList<Integer>(); dfs(num, 0, target, combination, results); return results; } private void dfs(int[] num, int index, int target, List<Integer> combination, List<List<Integer>> results) { if (target == 0) { results.add(new ArrayList<Integer>(combination)); return; } for (int i = index; i < num.length; i++) { if (i != index && num[i] == num[i - 1]) { continue; } if (num[i] > target) { break; } combination.add(num[i]); dfs(num, i + 1, target - num[i], combination, results); combination.remove(combination.size() - 1); } } }
第3题和第4题的区别只在于C中的每个数字可以使用几次，故第3题搜索从index开始：dfs(candidates, i, target - candidates[i], combination, results);第4题从index+1开始：dfs(num, i + 1, target - num[i], combination, results)。两题的共同点在解集不能包含重复的组合，故使用“选代表法”去重：if (i != index && candidates[i] == candidates[i - 1]) {continue;}
5.palindrome-partitioning（分割回文串）
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。返回s所有可能的回文串分割方案。
给出 s = "aab"，返回[["aa", "b"],["a", "a", "b"]]
DFS通常解法：
public class Solution { /** * @param s: A string * @return: A list of lists of string */ public List<List<String>> partition(String s) { // write your code here List<List<String>> results = new ArrayList<List<String>>(); if (s == null || s.length() == 0) { return results; } List<String> partition = new ArrayList<String>(); dfs(s, 0, partition, results); return results; } private void dfs(String s, int startIndex, List<String> partition, List<List<String>> results) { if (startIndex == s.length()) { results.add(new ArrayList<String>(partition)); return; } for (int i = startIndex; i < s.length(); i++) { String subString = s.substring(startIndex, i + 1); if (!isPalindrome(subString)) { continue; } partition.add(subString); dfs(s, i + 1, partition, results); partition.remove(partition.size() - 1); } } private boolean isPalindrome(String s) { for (int i = 0, j = s.length() - 1; i < j; i++, j--) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; } }
注意：从startIndex（初始为0）位置开始截取（startIndex, i+ 1）长度的子字符串判断是否为回文串，如果不是就i++，如果是就进行下一层dfs。结束条件为startIndex=s.length()-1
优化回文串判断的解法：
public class Solution { List<List<String>> results; boolean[][] isPalindrome; /** * @param s: A string * @return: A list of lists of string */ public List<List<String>> partition(String s) { results = new ArrayList<>(); if (s == null || s.length() == 0) { return results; } getIsPalindrome(s); helper(s, 0, new ArrayList<Integer>()); return results; } private void getIsPalindrome(String s) { int n = s.length(); isPalindrome = new boolean[n][n]; for (int i = 0; i < n; i++) { isPalindrome[i][i] = true; } for (int i = 0; i < n - 1; i++) { isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1)); } for (int i = n - 3; i >= 0; i--) { for (int j = i + 2; j < n; j++) { isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j); } } } private void helper(String s, int startIndex, List<Integer> partition) { if (startIndex == s.length()) { addResult(s, partition); return; } for (int i = startIndex; i < s.length(); i++) { if (!isPalindrome[startIndex][i]) { continue; } partition.add(i); helper(s, i + 1, partition); partition.remove(partition.size() - 1); } } private void addResult(String s, List<Integer> partition) { List<String> result = new ArrayList<>(); int startIndex = 0; for (int i = 0; i < partition.size(); i++) { result.add(s.substring(startIndex, partition.get(i) + 1)); startIndex = partition.get(i) + 1; } results.add(result); } }
注意：动态规划也可以判断回文字符串，回文串的子串也是回文串，比如p[i,j](表示以i开始以j结束的子串)是回文字符串，那么p[i+1,j-1]也是回文字符串。
int n = s.length(); boolean[][] isPalindrome = new boolean[n][n]; for (int i = 0; i < n; i++) { isPalindrome[i][i] = true; } for (int i = 0; i < n - 1; i++) {//判断相邻两个字符是否是回文串 isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1)); } for (int i = n - 3; i >= 0; i--) {//判断其余字符 for (int j = i + 2; j < n; j++) { isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j); } }
6.palindrome-partitioning-ii（分割回文串II）
给定一个字符串s，将s分割成一些子串，使每个子串都是回文。返回s符合要求的的最少分割次数。
排列搜索问题 Permutation
问题模型：求出所有满足条件的“ 排列”。判断条件：组合中的元素是顺序“ 相关”的。时间复杂度：与 n! 相关。
7.Chapter one 第4题 permutations(全排列）
8.Chapter one 第5题 permutations-ii（带重复元素的排列）
9.n-queens（N皇后）
n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击（任意两个皇后都不能放在同一行、同一列或同一斜线上）。给定一个整数n，返回所有不同的n皇后问题的解决方案。每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
class Solution { /** * Get all distinct N-Queen solutions * @param n: The number of queens * @return: All distinct solutions * For example, A string ‘...Q‘ shows a queen on forth position */ ArrayList<ArrayList<String>> solveNQueens(int n) { // write your code here ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>(); if (n <= 0) { return results; } search(results, new ArrayList<Integer>(), n); return results; } //寻找皇后放置的合适位置（cols存储每一行的列索引） private void search(ArrayList<ArrayList<String>> results, ArrayList<Integer> cols, int n) { if (cols.size() == n) { results.add(drawChessBoard(cols)); return; } for (int colIndex = 0; colIndex < n; colIndex++) { if (!isValid(cols, colIndex)) { continue; } cols.add(colIndex); search(results, cols, n); cols.remove(cols.size() - 1); } } //绘制棋盘 private ArrayList<String> drawChessBoard(ArrayList<Integer> cols) { ArrayList<String> chessboard = new ArrayList<String>(); for (int i = 0; i < cols.size(); i++) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < cols.size(); j++) { sb.append(j == cols.get(i) ? "Q" : "."); } chessboard.add(sb.toString()); } return chessboard; } //判断位置是否有效 private boolean isValid(ArrayList<Integer> cols, int column) { int row = cols.size(); for (int rowIndex = 0; rowIndex < cols.size(); rowIndex++) { if (cols.get(rowIndex) == column) { return false; } if (rowIndex + cols.get(rowIndex) == row + column) { return false; } if (rowIndex - cols.get(rowIndex) == row - column) { return false; } } return true; } };
注意：cols存储的是每一行放置皇后的列索引。search()函数寻找每一行中皇后放置的合适位置，列索引存储在cols中；drawChessBoard()函数绘制棋盘，皇后的位置绘制"Q"，其余位置绘制".:,要使用StringBuilder； isValid()函数判断该位置是否有效。
10.word-ladder-ii（单词接龙II）【hard】（Chapter four 第20题 word-ladder）
给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。每次只能改变一个字母。变换过程中的中间单词必须在字典中出现。所有单词具有相同的长度。所有单词都只包含小写字母。
11.string-permutation（字符串置换）
给定两个字符串，请设计一个方法来判定其中一个字符串是否为另一个字符串的置换。置换的意思是，通过改变顺序可以使得两个字符串相等。
public class Solution { /** * @param A a string * @param B a string * @return a boolean */ public boolean stringPermutation(String A, String B) { // Write your code here int[] cnt = new int[1000]; for (int i = 0; i < A.length(); i++) { cnt[(int) A.charAt(i)]++; } for (int j = 0; j < B.length(); j++) { cnt[(int) B.charAt(j)]--; } for (int i = 0; i < cnt.length; i++) { if (cnt[i] != 0) { return false; } } return true; } }
注意：使用一个数组，遍历A使得数组中相应位置的元素加1， 遍历B使得数组中相应位置的元素减1， 若最终数组中存在不为0的数则返回false。
12.permutation-index（排列序号）
给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。
13.permutation-index-ii（排列序号II）
给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。
14.next-permutation（下一个排列）
给定一个整数数组来表示排列，找出其之后的一个排列。排列中可能包含重复的整数。
注意：[1,2,7,4,3,1]的下一个排列是[1,3,1,2,4,7] 通过观察原数组可以发现，如果1.从末尾往前看，数字逐渐变大，到了2时才减小。再2.从后往前找第一个比2大的数字是3，3.交换2和3，再4.把此时3后面的所有数字转置一下即可。[1,2,7,4,3,1]->[1,2,7,4,3,1]->[1,3,7,4,2,1]->[1,3,1,2,4,7]
15.next-permutation-ii（下一个排列II）
给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。如果没有下一个排列，则输出字典序最小的序列。
16.previous-permutation（上一个排列）
给定一个整数数组来表示排列，找出其上一个排列。排列中可能包含重复的整数。
17.string-permutation-ii（字符串的不同排列）
给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。
18.word-break（单词划分）
给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
19.word-break-ii（单词划分II）【hard】
给定一个字符串s和一个单词字典dict，在s中添加空格来构造一个句子，其中每个单词都是有效的字典单词。返回所有这样的句子。
Chapter five Depth First Search（深度优先搜索）