# 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