[LeetCode] Edit Distance (Java)

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Analysis This is a DP problem. We will use a two dimensional array distance[][] … Read more [LeetCode] Edit Distance (Java)

[LeetCode] Rotate List (Java)

Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. Analysis This problem is not so difficult. We can use two pointers, a fast pointer and a slow pointer, to achieve this. However, there are some corner cases in this problem which needs to be careful. Take 1 -> … Read more [LeetCode] Rotate List (Java)

[LeetCode] Permutation Sequence (Java)

The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): “123” “132” “213” “231” “312” “321” Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive. Analysis We can generate all permutations until we get the kth one. But … Read more [LeetCode] Permutation Sequence (Java)

[LeetCode] Merge Intervals (Java)

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. Analysis We can sort the intervals first. They are sorted by their “start” value. If the “start” value is the same, “end” value is used to compare them. In Java, it’s very easy to sort them by writing a comparator. Code

Read more [LeetCode] Merge Intervals (Java)

[LeetCode] Jump Game and Jump Game II (Java)

Jump Game Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. Jump Game II Given an … Read more [LeetCode] Jump Game and Jump Game II (Java)

[LeetCode] Permutations and Permutations II (Java)

Permutations Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. Analysis It’s easy to implement Permutation recursively. In every level we use … Read more [LeetCode] Permutations and Permutations II (Java)