[LeetCode] Unique Binary Search Trees I and II (Java)

Unique Binary Search Trees Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s.

Unique Binary Search Trees II Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n. For example, Given n = 3, your program should return all 5 unique BST’s shown below.

Analysis … Read more…

[LeetCode] Decode Ways (Java)

A message containing letters from A-Z is being encoded to numbers using the following mapping:

Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12” is 2. Analysis We can solve this problem recursively. But it will time out. Because … Read more…

[LeetCode] Gray Code (Java)

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

Note: For a given n, a gray … Read more…

[LeetCode] Scramble String (Java)

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = “great”:

To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

We say … Read more…

[LeetCode] Search in Rotated Sorted Array II (Java)

Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. Analysis This problem is similar to “Search in Rotated Sorted Array”. But there could be duplicates. In problem “Search in Rotated Sorted Array”, we compare A[left] with … Read more…

[LeetCode] Word Search (Java)

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board =

word = “ABCCED”, -> returns true, word = “SEE”, -> returns true, word = “ABCB”, -> returns false. Analysis … Read more…

[LeetCode] Minimum Window Substring (Java)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”. Note: If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple such windows, you are guaranteed … Read more…

[LeetCode] Set Matrix Zeroes (Java)

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution? Analysis Using $O(mn)$ … Read more…

[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[][] to save the edit distance. … Read more…

[LeetCode] Sqrt(x) (Java)

Implement int sqrt(int x). Compute and return the square root of x. Analysis We can use binary search for this problem. It could be pretty easy to implement. It’s possible that integer overflows. So in the following code I use long type. There is another way, which is Newton’s Method. You can check the code here. Code

Complexity The complexity is … Read more…