Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = "aabcc", s2 = "dbbca"

  • When s3 = "aadbbcbcac", return true.
  • When s3 = "aadbbbaccc", return false.

 

Solution: Dynamic Programming
isInterleave[i][j] = if first i chars of s1 and first j chars of s2 is interleave of first i+j chars of s3
isInterleave[i][j] = isInterleave[i – 1][j] && s1.charAt(i – 1) == s3.charAt(i + j – 1))
|| (isInterleave[i][j – 1] && s2.charAt(j – 1) == s3.charAt(i + j – 1))

public boolean isInterleave(String s1, String s2, String s3) {
    if (s1 == null || s2 == null || s3 == null
            || s1.length() + s2.length() != s3.length()) {
        return false;
    }
    //isInterleave[i][j] = if first i chars of s1 and first j chars of s2
    //is interleave of first i+j chars of s3
    boolean[][] isInterleave = new boolean[s1.length() + 1][s2.length() + 1];
    isInterleave[0][0] = true;
    for (int i = 1; i <= s1.length(); i++) {
        isInterleave[i][0] = isInterleave[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
    }
    for (int j = 1; j <= s2.length(); j++) {
        isInterleave[0][j] = isInterleave[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
    }
    for (int i = 1; i <= s1.length(); i++) {
        for (int j = 1; j <= s2.length(); j++) {
            isInterleave[i][j] = (isInterleave[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                                 || (isInterleave[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
    return isInterleave[s1.length()][s2.length()];
}
FacebookTwitterGoogle+Share

Distinct Subsequences

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).

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

Solution: Dynamic Programming

Version 1. O(m*n)time O(m*n)space
f[i][j] means the number of different ways to select first j chars of T from first i chars from S, 即从S的前i个字符中挑出T的前j个字符 有多少种方案
f[i][j] = f[i-1][j-1] + f[i-1][j] //S[i]=T[j]
= f[i-1][j] //S[i]!=T[j]

public int numDistinct(String S, String T) {
    //f[i][j] means the number of different ways to select first j chars of T from first i chars from S
    //从S的前i个字符中挑出T的前j个字符 有多少种方案
    //f[i][j] = f[i-1][j-1] + f[i-1][j] //S[i]=T[j]
    //      = f[i-1][j] //S[i]!=T[j]
    if (S == null || T == null || S.length() < T.length()) {
        return 0;
    }
    int[][] numDistinct = new int[S.length() + 1][T.length() + 1];
    for (int i = 0; i <= S.length(); i++) {
        numDistinct[i][0] = 1;
    }
    for (int i = 1; i <= S.length(); i++) {
        for (int j = 1; j <= i && j <= T.length(); j++) {
            if (S.charAt(i - 1) == T.charAt(j - 1)) {
                numDistinct[i][j] = numDistinct[i - 1][j - 1] + numDistinct[i - 1][j];
            } else {
                numDistinct[i][j] = numDistinct[i - 1][j];
            }
        }
    }
    return numDistinct[S.length()][T.length()];
}

Version 2. O(m*n) time, O(n)space

just mod 2 for the row index. Rolling array.

public int numDistinct(String S, String T) {
    if (S == null || T == null || S.length() < T.length()) {
        return 0;
    }
    int[][] numDistinct = new int[2][T.length() + 1];
    for (int i = 0; i < 2; i++) {
        numDistinct[i][0] = 1;
    }
    for (int i = 1; i <= S.length(); i++) {
        for (int j = 1; j <= i && j <= T.length(); j++) {
            if (S.charAt(i - 1) == T.charAt(j - 1)) {
                numDistinct[i % 2][j] = numDistinct[(i - 1) % 2][j - 1] + numDistinct[(i - 1) % 2][j];
            } else {
                numDistinct[i % 2][j] = numDistinct[(i - 1) % 2][j];
            }
        }
    }
    return numDistinct[S.length() % 2][T.length()];
}

Edit Distance

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:

  • Insert a character
  • Delete a character
  • Replace a character
Example

Given word1 = "mart" and word2 = "karma", return 3.

Solution: Dynamic Programming

f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b[j]

= MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j]

intialize: f[i][0] = i, f[0][j] = j

answer: f[a.length()][b.length()]

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return -1;
    }
    //minDistance[i][j] = minimum distance to convert first i chars of word 1
    //to first j chars of word 2
    int[][] minDistance = new int[word1.length() + 1][word2.length() + 1];
    //init the first column -- word2 is empty
    for (int i = 0; i < minDistance.length; i++) {
        minDistance[i][0] = i;
    }
    //init the first row -- word1 is empty
    for (int j = 0; j < minDistance[0].length; j++) {
        minDistance[0][j] = j;
    }

    for (int i = 1; i <= word1.length(); i++) {
        for (int j = 1; j <= word2.length(); j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                minDistance[i][j] = Math.min(Math.min(minDistance[i - 1][j - 1],
                                minDistance[i - 1][j] + 1), minDistance[i][j - 1] + 1);
            } else {
                minDistance[i][j] = Math.min(Math.min(minDistance[i - 1][j - 1],
                                minDistance[i - 1][j]), minDistance[i][j - 1]) + 1;
            }
        }
    }
    return minDistance[word1.length()][word2.length()];
}

Unique Path II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Example

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note

m and n will be at most 100.

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    	// write your code here
    	if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0 || obstacleGrid[0][0] == 1) {
    		return 0;
    	}
    	int row = obstacleGrid.length;
    	int col = obstacleGrid[0].length;
    	int[][] path = new int[row][col];
    	path[0][0] = 1;
    	//init first col
    	for (int i = 1; i < row; i++) {
    		path[i][0] = obstacleGrid[i][0] == 1 ? 0 : path[i - 1][0];
    	}
    	//init first row
    	for (int j = 1; j < col; j++) {
    		path[0][j] = obstacleGrid[0][j] == 1 ? 0 : path[0][j - 1];
    	}
    	for (int i = 1; i < row; i++) {
    		for (int j = 1; j < col; j++) {
    			path[i][j] = obstacleGrid[i][j] == 1 ? 0 : path[i - 1][j] + path[i][j - 1];
    		}
    	}
    	return path[row - 1][col - 1];
    }

Lowest Common Ancestor

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

        4

/     \

3         7

/     \

5         6

For 3 and 5, the LCA is 4.

For 5 and 6, the LCA is 7.

For 6 and 7, the LCA is 7.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
    if (root == null || root == A || root == B) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, A, B);
    TreeNode right = lowestCommonAncestor(root.right, A, B);

    //both left and right are not null,
    //means A and B have to be in each of the subtrees
    if (left != null && right != null) {
        return root;
    }
    //if only left or right is not null,
    //means both A and B are in same subtree
    if (left != null) {
        return left;
    }
    if (right != null) {
        return right;
    }
    return null;
}

Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

  • Elements are visited in ascending order (i.e. an in-order traversal)
  • next() and hasNext() queries run in O(1) time in average.

Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 /    \
1      11
 \       \
  6       12

Challenge

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

1. Inorder Traverse the BST into an arrayList – O(n) space and O(n) time

public class Solution {
    //@param root: The root of binary tree.
    ArrayList<TreeNode> nodes;
    int index;
    public Solution(TreeNode root) {
        //flattern the tree using in-order traversal
        nodes = new ArrayList<>();
        inOrderTraversal(root, nodes);
        index = 0;
    }

    public void inOrderTraversal(TreeNode root, ArrayList<TreeNode> result) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left, result);
        result.add(root);
        inOrderTraversal(root.right, result);
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return index < nodes.size();
    }

    //@return: return next node
    public TreeNode next() {
        if (index < nodes.size()) {
            return nodes.get(index++);
        }
        return null;
    }
}

2. O(h) space – h is the height of the tree
Have a stack which only contains the left-most nodes and its ancestors, so that it takes O(h) space. And for each node, the average time complexity for next() is O(1).(Since the total time complexity is O(n))

public class Solution {
    //@param root: The root of binary tree.
    Stack<TreeNode> nodes;
    public Solution(TreeNode root) {
        nodes = new Stack<>();
        TreeNode runner = root;
        while (runner != null) {
            nodes.push(runner);
            runner = runner.left;
        }
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return !nodes.empty();
    }

    //@return: return next node
    public TreeNode next() {
        if (!nodes.empty()) {
            TreeNode curr = nodes.pop();
            if (curr.right != null) {
                TreeNode runner = curr.right;
                while (runner != null) {
                    nodes.push(runner);
                    runner = runner.left;
                }
            }
            return curr;
        }
        return null;
    }
}

3. O(1) space

Search Range in Binary Search Tree

Search Range in Binary Search Tree

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Example
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

20

/ \

8 22

/ \

4 12

public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
    ArrayList<Integer> result = new ArrayList<>();
    searchRangeHelper(root, k1, k2, result);
    return result;
}

public void searchRangeHelper(TreeNode root, int min, int max,
                              ArrayList<Integer> result) {
    if (root == null || min > max) {
        return;
    }
    if (root.val < min) {
        searchRangeHelper(root.right, min, max, result);
    } else if (root.val > max) {
        searchRangeHelper(root.left, min, max, result);
    } else {
        searchRangeHelper(root.left, min, root.val - 1, result);
        result.add(root.val);
        searchRangeHelper(root.right, root.val + 1, max, result);
    }
}

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

<code>  1
 / \
2   3
</code>

return 6.

private class maxPathResult {
    int maxSinglePath;
    int maxPath;
    public maxPathResult(int maxSinglePath, int maxPath) {
        this.maxSinglePath = maxSinglePath;//start from root to any nodes
        this.maxPath = maxPath;//max path in the tree
    }
}
public int maxPathSum(TreeNode root) {
    // write your code here
    return helper(root).maxPath;
}

public maxPathResult helper(TreeNode root) {
    if (root == null) {
        return new maxPathResult(Integer.MIN_VALUE, Integer.MIN_VALUE);
    }
    maxPathResult left = helper(root.left);
    maxPathResult right = helper(root.right);

    int maxSinglePath = Math.max(left.maxSinglePath, right.maxSinglePath);
    maxSinglePath = maxSinglePath < 0 ? root.val : root.val + maxSinglePath;

    int maxDoublePath = 0;
    if (left.maxSinglePath > 0) {
        maxDoublePath += left.maxSinglePath;
    }
    if (right.maxSinglePath > 0) {
        maxDoublePath += right.maxSinglePath;
    }
    maxDoublePath += root.val;

    int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), maxDoublePath);
    return new maxPathResult(maxSinglePath, maxPath);
}

计算树的最长path有2种情况:

1. 通过根的path.

(1)如果左子树从左树根到任何一个Node的path大于零,可以链到root上

(2)如果右子树从右树根到任何一个Node的path大于零,可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

所以创建一个inner class:

记录2个值:

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

注意,当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候,是不存在solution的。以免干扰递归的计算

九章详解

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

    public double findMedianSortedArrays(int[] A, int[] B) {
        if (A == null || B == null) {
            return -1; //or throw error
        }
        int size = A.length + B.length;
        if (size % 2 == 0) {
            return (findMedianHelper(A, 0, B, 0, size / 2) + findMedianHelper(A, 0, B, 0, size / 2 + 1)) / 2.0;
        } else {
            return findMedianHelper(A, 0, B, 0, size / 2 + 1);
        }
    }

    //find kth element from array A and B which starts from aStart and bStart
    public double findMedianHelper(int[] A, int aStart, int[] B, int bStart, int k) {
        if (aStart >= A.length) {
            return B[bStart + k - 1];
        }
        if (bStart >= B.length) {
            return A[aStart + k - 1];
        }
        if (k == 1) {
            return Math.min(A[aStart], B[bStart]);
        }

        int aPivot = aStart + k / 2 - 1 < A.length ? A[aStart + k / 2 - 1] : Integer.MAX_VALUE;
        int bPivot = bStart + k / 2 - 1 < B.length ? B[bStart + k / 2 - 1] : Integer.MAX_VALUE;

        if (aPivot < bPivot) {
            return findMedianHelper(A, aStart + k / 2, B, bStart, k - k / 2);
        } else {
            return findMedianHelper(A, aStart, B, bStart + k / 2, k - k / 2);
        }
    }

Follow Up Questions:

Now we have N machines, on each there is a sorted array, how to scale it to work together and efficiently find Kth element over all.

Solution 1:

N/2 group, each group has two machine. In each group, do only keep kth of two sorted array, then divide into n/4 groups, each group has 2 machine, keep kth of two sorted arrays again.

Time Complexity: O(K*lgN)

Solution 2:

二分答案S,将S广播给每台机器,每台机器用二分法求得有多少比该数小的数。汇总结果后可判断是该将S往上还是往下调整。总共最大的数是max, 最小的数是min,

s = (max+min)/2

然后你把s 拿到n台机器上去二分找有多少个数比他小, 如果有x个数比他小,

那么x< k 的话, min = s, x> k的话,max =s, 继续这个过程

Leetcode: Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int buyDay = -1; //keep track of the index of last buyDay
        int runner = 0;
        while (runner < prices.length-1) {
            if (runner + 1 < prices.length) {
                if (buyDay == -1 && prices[runner + 1] > prices[runner]) {
                    buyDay = runner;
                }
                if (buyDay != -1 && prices[runner + 1] < prices[runner]) {
                    maxProfit += prices[runner] - prices[buyDay];
                    buyDay = -1;
                }
            }
            runner++;
        }
        if (buyDay != -1 && prices[runner] > prices[buyDay]) {
            maxProfit += prices[runner] - prices[buyDay];
        }
        return maxProfit;
    }
}

Note:
Use a runner starting from the beginning of the array. Also need a variable called buyDay to keep track of the last buy day. -1 means there is no buy order yet or a sell order has just been placed, aka, next step is to buy. if buyDay equals to other integers, means next step is to sell.

When to Buy:
If next step is to buy and the price is increasing(means the price of next day is higher than the price of current day).

When to Sell:
If next step is to sell and the price is decreasing. the profit should be calculated and added to the maxProfit when sell order is placed.
Remember to check the edge cases, when it is the last day, there is no way to check if the price is increasing or decreasing. So just check if it has higher price than the buyDay.

Time Complexity:
O(n) only need to go through the array once.