学步园

Distinct Subsequences

Oct 19 '12

6266 / 17972

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 String;

import java.util.HashMap;

/**
 * @Title: Distinct_Subsequences.java
 * @Package String
 * @Description: TODO
 * @author nutc
 * @date 2013-9-1 下午3:16:51
 * @version V1.0
 */
public class Distinct_Subsequences {
	
	public static void main(String argsp[]){
		Distinct_Subsequences l = new Distinct_Subsequences();
		String s = "ddd";
		String t = "";
		System.out.println(l.numDistinct(s, t));
	}

	public int numDistinct(String S, String T) {
		if (S == null && T == null)
			return 0;
		if (S == null)
			return 0;
		if (T == null)
			return 1;
		if (S.equals(T))
			return 1;
		return compare(S, 0, T, 0);

	}

	HashMap<String, Integer> map = new HashMap<String, Integer>();

	public int compare(String s, int i, String t, int j) {
		if (i == s.length())
			return 0;
		if (j == t.length())
			return 1;//
		if (j == t.length() - 1 && i == s.length() - 1) {
			if (s.charAt(i) == t.charAt(j))
				return 1;
			else
				return 0;
		}

		int count = 0;
		if (s.charAt(i) == t.charAt(j)) {
			if (map.get((i + 1) + "-" + (j + 1)) != null)
				count += map.get((i + 1) + "-" + (j + 1));
			else
				count += compare(s, i + 1, t, j + 1);
		}
		if (map.get((i + 1) + "-" + (j)) != null)
			count += map.get((i + 1) + "-" + (j));
		else
			count += compare(s, i + 1, t, j);
		map.put(i + "-" + j, count);
		return count;
	}
}

但是其实想清楚的话 是很简单的！

public class Solution {
    public int numDistinct(String S, String T) {
        int m = T.length();
        int n = S.length();
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 1;
        for(int i=0;i<=m;i++)
            dp[i][0] = 0; //这两个初始值的区别
        for(int j=0;j<=n;j++)
            dp[0][j] = 1; //这两个初始值的区别
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if (T.charAt(i-1)==S.charAt(j-1))
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
                else
                    dp[i][j] = dp[i][j-1];
            }
        return dp[m][n];
    }
}