Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equals t.
Example: to reach the string "rabbit" there are 3 ways, by removing any of the three 'b's rabbbit
rabbbitrabbbit
public int numDistinct(String S, String T) {
// array creation
int[][] mem = new int[T.length()+1][S.length()+1];
// filling the first row: with 1s
for(int j=0; j<=S.length(); j++) {
mem[0][j] = 1;
}
// the first column is 0 by default in every other rows but the first, which we need.
for(int i=0; i<T.length(); i++) {
for(int j=0; j<S.length(); j++) {
if(T.charAt(i) == S.charAt(j)) {
mem[i+1][j+1] = mem[i][j] + mem[i+1][j];
} else {
mem[i+1][j+1] = mem[i+1][j];
}
}
}
return mem[T.length()][S.length()];
}Related Problems
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.