1/19, DFS, Search
特点：Find all possible solutions
DFS有迭代和递归两种实现方式。递归的执行是个程序压栈的过程，迭代是用Stack去模拟程序压栈的过程。
DFS的递归思想 --- 遍历和分治。
12/05复习补充
- 与Binary Tree DFS的比较
递归情况下，两者都是通过改变传递参数来实现DFS的。在Tree上的DFS通常改变TreeNode(root/root.left/root.right)，可以用迭代实现，也能用遍历或分治。不在Tree上的DFS通常要利用的是array(index)，多都是用遍历来做。
DFS 模板，通常是在main里用启动dfs()，在dfs()里可以通过for循环，以不同的参数来调用更多的dfs。for循环内可以使用if语句来作为入口条件，判断是否调用更多dfs。剩下就是设置出口，通常要判断下，当参数满足某个条件就return。当使用全局变量如visited matrix时，如果需要，在dfs结束后reset全局变量。
从某个角度讲都是一样的算法，不用细究这些概念的名字。
- 递归 Recursion
- 深度优先搜索 Depth First Search
- 回溯 Backtracking
Subsets
- 遍历 ✔️
- 复杂度分析 ✔️
要排除因为排序不同产生的结果，使用index去重。
define what subsets is or to clarify it - permutations are same combination, and solution contains no duplicated combinations.
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
List<Integer> list = new ArrayList<>();
dfs(nums, 0, list, res);
return res;
}
private void dfs(int[] nums, int start, List<Integer> list, List<List<Integer>> res) {
res.add(new ArrayList<>(list));
for (int i = start; i < nums.length; i++) {
list.add(nums[i]);
dfs(nums, i + 1, list, res);
list.remove(list.size() - 1);
}
}
}
DFS的时间复杂度 = 构造每个答案的时间复杂度 * 所有答案的个数 = O(n * 2^n)。
空间复杂度是O(n)，因为num(dfs function call) = max depth(recursion tree) = n。
这里不使用实例属性也可以，因为res是mutable object。
Subsets II
输入contain duplicates，返回的集合里不能有duplicated subset，所以check before push in。
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null) return res;
List<Integer> list = new ArrayList<>();
Arrays.sort(nums);
dfs(res, list, nums, 0, new boolean[nums.length]);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, int start, boolean[] visited) {
res.add(new ArrayList<>(list));
for (int i = start; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
visited[i] = true;
list.add(nums[i]);
dfs(res, list, nums, i + 1, visited);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
Permutations
- 遍历 ✔️
- 复杂度分析 ✔️
不同的排序是不同的结果。因此不需要使用index，只要判断下nums.length == list.size() 做为出口条件就可以了。
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null) return res;
List<Integer> list = new ArrayList<>();
dfs(res, list, nums, new boolean[nums.length]);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] visited) {
if (nums.length == list.size()) {
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
list.add(nums[i]);
dfs(res, list, nums, visited);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
}
时间复杂度 = O(n * n!)。
还可以换成得到所有字母的不同组合，一个套路。
Permutations II
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null) return res;
Arrays.sort(nums);
List<Integer> list = new ArrayList<>();
dfs(res, list, nums, new boolean[nums.length]);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] visited) {
if (nums.length == list.size()) {
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
if (!visited[i]) {
visited[i] = true;
list.add(nums[i]);
dfs(res, list, nums, visited);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
}
next permutation
the idea is that starting from the end, find the first element that is not sorting in descending order, record the index, say i, and starting from the end again, find the first element that is larger than the value in ith index. say j. Swap the data in i and j. Finally, reverse the numbers right to the number i. We should note that we add the if (i >= 0) to avoid the overflow. consider the corner case like [3], []...
public void nextPermutation(int[] nums) {
if (nums == null) return;
int i = nums.length - 2;
while (i >= 0 && nums[i] > nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1);
}
private void reverse(int[] arr, int left, int right) {
int i = left, j = right;
while (i < j) {
swap(arr, i, j);
i++;
j--;
}
}
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
Combination Sum
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
if (candidates == null || candidates.length == 0) return res;
List<Integer> list = new ArrayList<>();
dfs(res, list, candidates, target, 0);
return res;
}
void dfs(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start) {
if (target < 0) return;
if (target == 0) {
res.add(new ArrayList<>(list));
return;
}
for (int i = start; i < candidates.length; i++) {
list.add(candidates[i]);
dfs(res, list, candidates, target - candidates[i], i);
list.remove(list.size() - 1);
}
}
}
和subsets II同样的思路，区别是同一个element可以使用多次，要用index参数guarantee不会用index之前的elements。要特别注意需要一个递归入口，去终止无限的dfs调用。
12/06复习，遗漏了出口的条件。
12/23复习注，上面这些问题都要考虑去重，而重复的解可能是由于array中的重复元素造成的，也可能是由dfs得到的。像上面这题array中如果有重复元素，且每个元素都可以重复使用，就一定会得到重复的解，因此递归出口会去排除。
2/3补充，有很多clarification需要提，
- is it possible to choose the same number from input more than once? no:boolean[] visited
- could the solution set contain duplicated combinations? if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
- are permutations duplicated combination?
- do we need to consider the situation where the input candidates is empty, and if so, is the output a list of empty list or just None?
factor combinations
这道题思路比较清晰，注意的点是dfs的base case如何设计
class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<>(), n, 2);
return res;
}
private void dfs(List<List<Integer>> res, ArrayList<Integer> list, int n, int start) {
if (n == 1) {
if (list.size() > 1) { // need to remove the situation where the num is prime.
res.add(new ArrayList<>(list));
return;
}
}
for (int i = start; i <= n; i++) {
if (n%i == 0) {
list.add(i);
dfs(res, list, n/i, i);
list.remove(list.size() - 1);
}
}
}
}
basically, we can optimize the original program:
class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<>();
if (n <= 1) return res;
dfs(res, new ArrayList<>(), n, 2);
return res;
}
32 2
private void dfs(List<List<Integer>> res, List<Integer> list, int num, int start) {
for (int i = start; i * i <= num; ++i) {
if (num % i == 0) {
list.add(i);
list.add(num / i);
res.add(new ArrayList<>(list));
list.remove(list.size() - 1);
dfs(res, list, num / i, i);
list.remove(list.size() - 1);
}
}
}
}
Valid Sudoku
create three 2D boolean array to represent the status for each cell in three different directions, row, col, and cube.
Note that, for the cube, we only need to care about the row...
class Solution {
public boolean isValidSudoku(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return false;
int m = board.length;
int n = board[0].length;
boolean[][] vert = new boolean[m][n];
boolean[][] hori = new boolean[m][n];
boolean[][] cube = new boolean[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == '.') continue;
int val = board[i][j] - '1';
if (vert[j][val] || hori[i][val] || cube[(i/3) * 3 + j/3][val]) return false;
vert[j][val] = true;
hori[i][val] = true;
cube[(i/3) * 3 + j/3][val] = true;
}
}
return true;
}
}
Sudoku Solver
和number of islands题的区别是number of islands 不用还原，而sudoku做错了是要还原的。所以DFS需要返回一个boolean。还有就是和valid sudoku一样，我们用三个boolean array来check是否是合理的sudoku，用index来表示我走到哪儿了。
class Solution {
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0 || board.length == 0) return;
solver(board);
}
public boolean solver(char[][] board) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] != '.') continue;
for (char c = '1'; c <= '9'; ++c) {
if (isValid(board, i, j, c)) {
board[i][j] = c; // put c for this cell
if (solver(board)) {
return true;
} else {
board[i][j] = '.';
}
}
}
return false; // for the given cell with the period character
}
}
return true; // explore all the board and find no empty cells
}
private boolean isValid(char[][] board, int row, int col, char c) {
int blockRow = (row/3)*3, blockCol = (col/3)*3;
for (int i = 0; i < 9; ++i) {
if (board[row][i] == c || board[i][col] == c ||
board[blockRow + i/3][blockCol + i%3] == c) {
return false;
}
}
return true;
}
}
N queens
这道题跟上一题的区别是每一行只要填一个Q，所以只要一个level表示行数就可以了。 另外，由于对称性和处理的顺序，我只要check四个方向就可以了。 另外，我可以最后统一输出结果会更加简洁。也可以把List<String> list 做为参数带给dfs一起处理。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
dfs(res, board, 0);
return res;
}
private void dfs(List<List<String>> res, char[][] board, int level) {
if (level == board.length) {
List<String> list = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < board[0].length; j++) {
sb.append(board[i][j]);
}
list.add(sb.toString());
}
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < board.length; i++) {
board[level][i] = 'Q';
if (isValid(board, level, i)) {
dfs(res, board, level + 1);
}
board[level][i] = '.';
}
}
private boolean isValid(char[][] board, int row, int col) {
for (int i = row - 1; i >= 0; i--) {
if (board[i][col] == 'Q') {
return false;
}
}
for (int i = col - 1; i >= 0; i--) {
if (board[row][i] == 'Q') {
return false;
}
}
for (int i = col - 1, j = row - 1; i >= 0 && j >= 0; i--, j--) {
if (board[j][i] == 'Q') {
return false;
}
}
for (int i = col + 1, j = row - 1; i < board[0].length && j >= 0; i++, j--) {
if (board[j][i] == 'Q') {
return false;
}
}
return true;
}
}
word search
2D input，类似Number of Islands的棋盘类, 是DFS flooding filling。首先要在board上找到和word[0]相同的字母，然后做dfs。因为相同的字母不能重复使用，要用visited matrix保存访问过的点。
在dfs过程中，check 3 status:
下一个字母不超过边界
下一个字母和word下一个字母相同(在word上用个index同步就行了)
下一个字母没被访问过
实际上，每个递归都可以往4个方向递归，上下左右可以try，这点也和number of island很像。要注意的是，如果四个方向都走不通，要把visited重置成False，因为在一个方向的尝试，会修改visited，会影响到其他方向的可能性。
class Solution {
// dfs + backtracking problem
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) return false;
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n]; // same letter cannot be reused during a single search.
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0) && !visited[i][j]) {
if (dfs(board, word, 0, i, j, visited)) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, int row, int col, boolean[][] visited) {
if (index == word.length()) {
return true;
}
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length
|| board[row][col] != word.charAt(index) || visited[row][col]) return false;
visited[row][col] = true;
for (int[] pair : pairs) {
int x = pair[0] + row;
int y = pair[1] + col;
if (dfs(board, word, index + 1, x, y, visited)) {
return true;
}
}
visited[row][col] = false;
return false;
}
private int[][] pairs = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
}
1/3复习补充，这题思路去类比number of islands，都是在主函数内检查matrix的每个位置，然后drive dfs。对于一个可以dfs的位置，检查它的4 neighbors是否能继续dfs。和N-Queens一样，需要clear up。对visited的clear是因为考虑到matrix里，可以和word[0]重复的不止一个位置，所以用局部的dfs把visited重置。
1/23，一直没注意是尾递归，差不多是onsite coding的难度。
what is the time complexity?
- after considering the start node, we get the time complexity: O(num_of_word[0]_in_board * 4^L), in worst case, is O(n*m * 4^L) // L is the length of the String word,
- why? first we just think to search 4 directions beside the current cell. This quadtree's height is L(L is length of word) and its total node number is 4^0 + 4^1 + ... + 4^L = 1/3 * ( 4^(L+1) - 1 ). So the time complexity of this dfs solution is O(4^L).
- It seems that an algorithm with O(4^n) time complexity must be TLE. Actually, it's true. That's why we add the visited array to memorize those visited cells in order to prune the quadtree. Another pruning is to cut down those illegal node, such as board[0,-1] and board[-1,0] in the example above. After these pruning, we get AC!
number of islands
这道题跟word search 最大的区别在于，number of islands 下一次搜索是基于上一次搜索的结果的。所以不用backtracking.
可以用DFS也可以用BFS，需要明确，是否可以更改matrix，
DFS version without modification:
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
count++;
dfs(grid, i, j, visited);
}
}
}
return count;
}
public void dfs(char[][] grid, int row, int col, boolean[][] visited) {
// base case
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || visited[row][col] || grid[row][col] == '0') return;
// recursive case
visited[row][col] = true;
for (int[] pair : pairs) {
int x = pair[0] + row;
int y = pair[1] + col;
dfs(grid, x, y, visited);
}
}
private final int[][] pairs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
}
BFS version without modification
class Solution {
private void bfs(char[][] grid, int row, int col, boolean[][] visited) {
Deque<int[]> queue = new LinkedList<>();
queue.offer(new int[]{row, col});
//grid[row][col] = '0'; // can modify grid
visited[row][col] = true;
while(!queue.isEmpty()) {
int[] node = queue.poll();
for (int[] pair : pairs) {
int x = pair[0] + node[0];
int y = pair[1] + node[1];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1' && !visited[x][y]) {
queue.offer(new int[]{x, y});
//grid[x][y] = '0'; // can modify grid
visited[x][y] = true;
}
}
}
}
private int[][] pairs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
}
如果要算max area, 用DFS, 返回这个区域相连的1的数量。
private static int dfs(int[][] matrix, int i, int j){
if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] == 0){
return 0;
}
matrix[i][j] = 0;
int size = 1;
for(int[] dir : dirs){
int x = i + dir[0];
int y = j + dir[1];
size += dfs(matrix, x, y);
}
return size;
}
Number of Distinct Islands
the key to this problem is to determine what is distinct islands. We use HashSet to store the route path. Specifically, we just store the direction string. But we should note that the end of DFS method should add the "back" information because we should differentiate some situations.like
// 1 - 1 - 1 and 1 - 1
// | |
// 1 1 - 1
class Solution {
public int numDistinctIslands(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
Set<String> set = new HashSet<>(); // store the direction string...
for (int i= 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (grid[i][j] == 1) {
StringBuilder sb = new StringBuilder();
dfs(grid, i, j, sb, "o"); // origin
grid[i][j] = 0;
set.add(sb.toString());
}
}
}
return set.size();
}
private void dfs(int[][] grid, int row, int col, StringBuilder sb, String dir) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) {
return;
}
sb.append(dir);
grid[row][col] = 0;
dfs(grid, row - 1, col, sb, "u");
dfs(grid, row + 1, col, sb, "d");
dfs(grid, row, col - 1, sb, "l");
dfs(grid, row, col + 1, sb, "r");
sb.append("b"); // back
}
}
Time and Space complexity is O(R * C). where RR is the number of rows in the given grid, and CC is the number of columns. We visit every square once.
All Nodes Distance K in Binary Tree
Tree distance problems, need to use DFS to solve the problems.