编程题 40 /85

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？

字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
例如：

S="nowcccoder", T = "nowccoder"

返回3

参考答案

Java版本代码1

import java.util.*;

public class Solution {
    public int numDistinct (String S, String T) {
        // write code here
        char[] s = S.toCharArray();
		char[] t = T.toCharArray();
		int[][] dp = new int[s.length + 1][t.length + 1];
		for (int j = 0; j <= t.length; j++) {
			dp[0][j] = 0;
		}
		for (int i = 0; i <= s.length; i++) {
			dp[i][0] = 1;
		}
		for (int i = 1; i <= s.length; i++) {
			for (int j = 1; j <= t.length; j++) {
				dp[i][j] = dp[i - 1][j] + (s[i - 1] == t[j - 1] ? dp[i - 1][j - 1] : 0);
			}
		}
		return dp[s.length][t.length];
    }
}

Java版本代码2

import java.util.*;

public class Solution {
    public int numDistinct (String S, String T) {
        // write code here
        char[] s = S.toCharArray();
		char[] t = T.toCharArray();
		int[] dp = new int[t.length + 1];
		dp[0] = 1;
		for (int j = 1; j <= t.length; j++) {
			dp[j] = 0;
		}
		for (int i = 1; i <= s.length; i++) {
			for (int j = t.length; j >= 1; j--) {
				dp[j] += s[i - 1] == t[j - 1] ? dp[j - 1] : 0;
			}
		}
		return dp[t.length];// write code here
    }
}

纠错收藏

查看讨论

1
...
35
36
37
38
39
40
41
42
43
44
45
...
85
跳转到

上一题下一题