Distinct Subsequences | Leetcode

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.

---

Solution: I probably felt fortunate that I didn't try to crack my head trying to come up with my own solution. This is a non-trivial 2D dynamic programming problem. If you use brute force, it will not pass large tests in leetcode.

Good detailed explanation can be found in stackoverflow: http://stackoverflow.com/questions/20459262/distinct-subsequences-dp-explanation

public class Solution {
    public int numDistinct(String s, String t) {
        int[] f = new int[t.length() + 1];
        f[t.length()] = 1;

        for (int si = s.length() - 1; si >= 0; si--) {
            for (int ti = 0; ti < t.length(); ti++) {
                if (s.charAt(si) == t.charAt(ti)) {
                    f[ti] += f[ti + 1];
                }
            }
        }
        
        return f[0];
    }
}