The Problem:
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
.
Notes:
- Here when seeing only required to return the number of ways (not the entire list of ways), we could consider DP instead of pure recursion. use match[i][j] to represent number of distinct sub sequence that S[0-i] has for T[0-j] seems a good start.
- As for the recurrence formula, if S[i]!=T[j], then simply means S[i] is not used for the match (match[i][j] = match[i-1][j]). if(S[i]=T[j]), then we can consider the number of ways comes from two paths: use S[i] (match[i][j] = match[i-1][j-1]); and not use S[i] (match[i][j] = match[i-1][j]).
- Watch out for the details and edge cases.
Java Solution
public class Solution { public int numDistinct(String S, String T) { int slen = S.length(); int tlen = T.length(); // check length if(slen==0 || slen < tlen) return 0; if(tlen==0) return 1; // record dist. subseqs of t[0-j] in in s[0-i] in match[i][j] int[][] match = new int[slen][tlen]; for(int i = 0; i < slen; i++){ for(int j = 0; j < tlen; j++){ if(i < j) match[i][j] = 0; else if(i==0 && j==0){ match[i][j] = S.charAt(0)==T.charAt(0)? 1:0; } else if(S.charAt(i)==T.charAt(j)){ //divide case by either use s[i] or not // only consider j=0 case, i=0 already covered in previous conditions: //1. i<j 2. i==0&& j==0 if(j==0) match[i][j] = match[i-1][j]+1; else match[i][j] = match[i-1][j-1] + match[i-1][j]; } else{ match[i][j] = match[i-1][j]; } } } return match[slen-1][tlen-1]; } }
Advertisements