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.

	package leetcode.dp;
	/**
	* Solution: DP. Time O(m*n) Space O(m*n) --> 可以用一位数组，只维护T的 O(n)
	* 题目感觉不是那么好理解，还有注意是序列，不是子串，顺序一致即可。
	* S i 和 T j 不相同 -> nums[i][j] = nums[i-1][j] i的出现不会影响结果.
	* S i 和 T j 相同 -> nums[i][j] = nums[i-1][j-1] + nums[i-1][j] 需要加上之前满足的结果.
	*
	* Reference:
	* http://fisherlei.blogspot.com/2012/12/leetcode-distinct-subsequences_19.html
	* http://codeganker.blogspot.com/2014/04/distinct-subsequences-leetcode.html
	*
	* @author jeffwan
	* @date Apr 15, 2014
	*/
	public class NumDistinct {
	public int numDistinct(String S, String T) {
	if (S == null || T == null) {
	return 0;
	}
	int[][] nums = new int[S.length() + 1][T.length() + 1];
	for (int i = 0; i < S.length(); i++) {
	nums[i][0] = 1;
	}
	for (int i = 1; i <= S.length(); i++) {
	for (int j = 1; j <= T.length(); j++) {
	nums[i][j] = nums[i - 1][j];
	if (S.charAt(i - 1) == T.charAt(j - 1)) {
	nums[i][j] += nums[i - 1][j - 1];
	}
	}
	}
	return nums[S.length()][T.length()];
	}
	}

view raw NumDistinct.java hosted with ❤ by GitHub