[LeetCode] Distinct Subsequences (Java)

Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not). Here is an example: S = “rabbbit”, T = “rabbit” Return 3. Analysis This is … Read more…

[LeetCode] Recover Binary Search Tree (Java)

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? Analysis We can use in-order traverse to find the swapped element. During the traverse, we can find the element that is smaller than the previous … Read more…

[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…