Distinct Subsequences (Java)

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.

Solution: when see question about two strings , DP should be considered first. we can abstract this question to calculate appear times for string T with length i in string S with length j, which can be represented by numbers[i][j], then through observation and thinking , we can know for numbers[i][j] it should at least equal the numbers[i][j-1] and if T.charAt(i)==S.charAt(j) , numbers[i][j] should also be add numbers[i-1][j-1]

	/*
	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.
	*/
	public class DistinctSubsequences {
	public int numDistinct(String S, String T) {
	if (S==null||S.length()==0||T==null&&T.length()==0){
	return 0;
	}
	if (S.length()<T.length()){
	return 0;
	}
	int[][] nums=new int[T.length()+1][S.length()+1];
	for (int row=0; row<nums.length;row++){
	// appear numbers of String T in String "";
	nums[row][0]=0;
	}
	for (int col=0; col<nums[0].length; col++){
	// appears numbers of String "" in String S;
	nums[0][col]=1;
	}
	for (int row=1; row<nums.length; row++){
	for (int col=1; col<nums[0].length; col++){
	// no matter if current char in S equal to current char in T
	// current matched times is at least equal to the times matched between T and S.substring(0, index(current Char))
	nums[row][col]=nums[row][col-1];
	// if current char in T matched current char in S, then nums[row][col] should also plus
	// the times matched between T.substring(0,index(current char) ) and S.substring(0, index(current char));
	if (S.charAt(col-1)==T.charAt(row-1)){
	nums[row][col]+=nums[row-1][col-1];
	}
	}
	}
	return nums[T.length()][S.length()];
	}
	}

view raw DistinctSubsequences.java hosted with ❤ by GitHub