leetcode: Distinct Subsequences

Problem Description:

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 and Precautions:

DP: let F(i, j) denote the number of ways for S[0]…S[i] contain T[0]..T[j], Then F(n-1, m-1) is our answer and we have
if(S[i] != T[j])  F(i, j) = F(i-1, j);
if(S[i] == T[j]) F(i, j) = F(i-1, j-1) + F(i-1, j);

Tips and Divergent thinking:

Be careful on the base case, and for the above recursive definition, recursive implementation might be easier to maintain than for loops.

Written on June 5, 2013