When we have a string pattern and want to match it with the substring of a given string, what can we do? The tuition way is that we could use substring() to match in a for loop. But the Time Complexity would be O(N* L), N refer to the string length, L refer to the …
Edit Distance
The edit distance algorithm is very popular among the data scientists. It’s one of the basic algorithms used for evaluation of machine translation and speech recognition. The naive approach would be to check for all possible edit sequences and choose the shortest one in-between. That would result in an exponential complexity and it’s an overkill …
Recover Binary Search Tree
This is No.99 in LeetCode. Here are approaches to this problem: Approach 1: Sort an Almost Sorted Array Where Two Elements Are Swapped Algorithm Here is the algorithm: Construct inorder traversal of the tree. It should be an almost sorted list where only two elements are swapped. Identify two swapped elements x and y in …
Sort List
This is No.148 Problem in LeetCode. Here are two approaches as below: Top Down Merge Sort Recursively split the original list into two halves. The split continues until there is only one node in the linked list (Divide phase). To split the list into two halves, we find the middle of the linked list using …
Course Schedule II
This is No.210 in LeetCode. I can’t solve this problem by self, but I found a real solid solution and explanation. This is our "main" function: public int[] findOrder(int numCourses, int[][] prerequisites) { int[] incLinkCounts = new int[numCourses]; // incoming edges List<List<Integer>> adjs = new ArrayList<>(numCourses); initialiseGraph(incLinkCounts, adjs, prerequisites); //return solveByBFS(incLinkCounts, adjs); return solveByDFS(adjs); } …
Perfect Squares
This in No.279 in LeetCode. The math theory is: dp[0] = 0 dp[1] = dp[0]+1 = 1 dp[2] = dp[1]+1 = 2 dp[3] = dp[2]+1 = 3 dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 } = Min{ dp[3]+1, dp[0]+1 } = 1 dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 } = Min{ dp[4]+1, dp[1]+1 } = 2 . . …
Number of Islands
This is No.200 in LeetCode. The solution is below: public class Solution { private int y; private int x; public int numIslands(char[][] grid) { int res = 0; y = grid.length; if (y == 0) return 0; x = grid[0].length; for (int i = 0; i < y; i++){ for (int j = 0; j …
Circular Array Loop
This is No.457 in LeetCode. The solution is post below: public class Solution { public boolean circularArrayLoop(int[] nums) { if (nums == null || nums.length < 2) return false; int n = nums.length; for (int i = 0; i < n; i++) { if (nums[i] == 0) { continue; } // slow/fast pointer int j …
Longest Increasing Subsequence
This No.300 in LeetCode. Here are two approaches for this problem, I will introduce both of them here. Dynamic Programming – O(n^2) The first solution using Dynamic Programming. We will create a one-dimension dp array. We will go over the whole array, and store the numbers of greater number in dp array. class Solution { …
This is No.63 in Leetcode. My original solution is: class Solution { private int path = 0; public int uniquePathsWithObstacles(int[][] obstacleGrid) { // get i and j int i = obstacleGrid[0].length; int j = obstacleGrid.length; i–; j–; findPath(i, i, path, obstacleGrid); return path; } private void findPath(int i, int j, int path, int[][] obstacleGrid){ // …