[LeetCode] 115. 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).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Thought process:

1. Sub-problem: count the number of distinct subsequences of a substring of T and a substring of S.
2. Function: 
1. If the last character of S and T are not the same, the last character of S will not contribute to the subsequences. f[i][j] = f[i - 1][j].
2. Otherwise, we add the number of subsequences where the last character of S is in. f[i][j] = f[i - 1][j] + f[i - 1][j - 1].
3. Initialization: 
1. If T is empty, there is one way to get an empty string out of S, which is to choose nothing. f[i][0] = 1.
2. If S is empty and T is not, there is no way to get T out of S. f[0][j] = 0.
4. Answer: f[s.length][t.length].

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public class Solution { public int numDistinct(String s, String t) { int sLength = s.length(); int tLength = t.length(); int[][] f = new int[sLength + 1][tLength + 1]; for (int i = 0; i <= sLength; i++) { f[i][0] = 1; } for (int i = 1; i <= sLength; i++) { for (int j = 1; j <= tLength; j++) { if (s.charAt(i - 1) == t.charAt(j - 1)) { f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; } else { f[i][j] = f[i - 1][j]; } } } return f[sLength][tLength]; } }

Time complexity: 

Say m = t.length and n = s.length, the overall time complexity is O(mn).