Can anybody explain a little bit of the BFS DFS question? Why BFS uses more memory than DFS does?
GaoLiaoLiao
@GaoLiaoLiao
Posts made by GaoLiaoLiao

RE: C++ clean solution, answers to follow up

RE: C++ clean solution, answers to follow up
Explanation for the time complexity:
suppose you have n files and the average length of each file is k.
the worst case is that all the files are have the same size and the content of the files are basically the same. In that case, you need to compare every file with all the other files.File A: "AAAAAAAAAAA"
File B: "AAAAAAAAAAB"
File C: "AAAAAAAAAAC"
File D: "AAAAAAAAAAD"here you need to:
compare A with B,C,D.
compare B with C,D.
compare C with D.
which means you need to compare (n^2)/2 times.
And for each compare, you need to compare k chars.
In conclusion, the time complexity is O((n^2)*k) 
Java Recursive Solution, similar to 394. Decode String
int index = 0; public TreeNode str2tree(String s) { if(s.isEmpty()) { return null; } TreeNode root = new TreeNode(0); int num = 0; int sign = 1; while(index < s.length() && s.charAt(index) != ')') { char ch = s.charAt(index); if(ch == '') { sign = 1; index++; } else if(ch >= '0' && ch <= '9') { num = num * 10 + ch  '0'; index++; } else if(ch == '(') { // skip '(' index++; // process node TreeNode child = str2tree(s); // skip ')' index++; if(root.left == null) { root.left = child; } else { root.right = child; } } } root.val = sign * num; return root; }

RE: Java Binary Search O(log(n)) Shorter Than Others
@rishavrastogi Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

RE: Explanation of why those posted algorithms are mathematically valid
Thank you! excellent explanation!

RE: Java simple DFS with memorization
@guolei329 Thanks for your for explanation! (But I still don't know how to analyze the time complexity of this method.)

RE: Similar to The Maze. Easyunderstanding Java bfs solution.
// thanks for sharing! very inspiring! // changed a little bit of your code and improve the runtime to about 20ms public static final int[][] dirs = new int[][] {{1, 0}, {0, 1}, {1, 0}, {0, 1}}; public int shortestDistance(int[][] maze, int[] start, int[] destination) { if(maze == null  maze.length == 0  maze[0].length == 0) { return 1; } int m = maze.length; int n = maze[0].length; int[][] dp = new int[m][n]; Queue<Pair> que = new LinkedList<>(); que.offer(new Pair(start[0], start[1], 0)); for(int i = 0; i < m; i++) { Arrays.fill(dp[i], Integer.MAX_VALUE); } while(!que.isEmpty()) { Pair cur = que.poll(); for(int[] dir : dirs) { int nextX = cur.x; int nextY = cur.y; int len = cur.len; while(nextX < m && nextX >= 0 && nextY < n && nextY >= 0 && maze[nextX][nextY] == 0) { nextX += dir[0]; nextY += dir[1]; len++; } nextX = dir[0]; nextY = dir[1]; len; // avoid going through unneccessary cases. if(len > dp[destination[0]][destination[1]]) { continue; } if(len < dp[nextX][nextY]) { dp[nextX][nextY] = len; que.offer(new Pair(nextX, nextY, len)); } } } return dp[destination[0]][destination[1]] == Integer.MAX_VALUE ? 1 : dp[destination[0]][destination[1]]; } class Pair { int x; int y; int len; public Pair(int x, int y, int len) { this.x = x; this.y = y; this.len = len; } }

RE: Java simple DFS with memorization
I come up with the same idea. But what is the time complexity for this method? I'm always confused about the complexity analysis when using memorization. Can anyone tell me?

Recusive Java solution O(h) time
public TreeNode deleteNode(TreeNode root, int key) { if(root == null) { return null; } if(root.val < key) { TreeNode tmp = deleteNode(root.right, key); root.right = tmp; return root; } else if(root.val > key) { TreeNode tmp = deleteNode(root.left, key); root.left = tmp; return root; } else { return delete(root); } } public TreeNode delete(TreeNode target) { if(target.left == null) { return target.right; } TreeNode tmp = target.left; while(tmp.right != null) { tmp = tmp.right; } tmp.right = target.right; return target.left; }