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 …

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 …

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){ // …