问题描述:
给定两个字符串S和T,返回S子序列等于T的不同子序列个数有多少个? 如果得到子序列A删除的位置与得到子序列B删除的位置不同,那么认为A和B就是不同的。
【例子】
S = "rabbbit", T = "rabbit"
返回: 3
是以下三个S的不同子序列,没有^的位置表示删除的位置,因为删除的位置不同,所以这三 个子序列是不一样的
rabbbit
I I I I II
rabbbit
I I I I II
rabbbit
I I I I II
思想:
看到题目题目中有两个字符串,讨论字符串之间的某种关系时,我们首先想到的是建立一张二维数组。
建立二维数组dp[i][j],其含义是字符串S的0~i的子数组上随便删除得到的子序列与字符串T的0~j的子数组相同的方法数。
二维数组第一行dp[0][j] 表示的含义是:字符串S第一个字符随便删除,变为字符串T的0~j的字符的方法数。我们知道只有第一个位置如果相等有一种方法,其他位置方法数为0。
二维数组第一列dp[i][0] 表示的含义是:字符串S的0~i位置字符随便删除得到字符串T的第一个字符。dp[0][0]如果字符串T的第一个字符与字符串T的第一个字符相同则为1,不同则为0。字符串S的i位置字符与字符串S的第一个字符相同,则dp[i-1][0]+1,否则为dp[i-1][0]。
对于二维数组的普遍位置dp[i][j]分为两种情况:
1> 字符串S的第i个字符是处于删除状态时,dp[i][j] = dp[i-1][j] 。
2> 字符串S的第i个字符是处于保留状态时,也就是S[i] = T[j],dp[i][j] = dp[i-1][j-1]
代码:
public static int maxSubSeqNum(String s,String t){if((s == null && t == null) || ("".equals(s) && "".equals(t))){return 1;}if((s == null && t != null) || s.length() < t.length()){return 0;}char[] sA = s.toCharArray();char[] tA = t.toCharArray();int[][] dp = new int[s.length()][t.length()];dp[0][0] = sA[0] == tA[0] ? 1 : 0;// dp[0][j] 其他不用填默认0// 列for (int i = 1; i < sA.length; i++) {dp[i][0] = sA[i] == tA[0] ? dp[i-1][0] + 1 : dp[i-1][0];}for (int i = 1; i < sA.length; i++) {for (int j = 1; j < tA.length; j++) {dp[i][j] = dp[i-1][j] + (sA[i] == tA[j] ? dp[i-1][j-1] : 0);}}return dp[sA.length-1][tA.length-1];}public static void main(String[] args) {String s = "abcvcabc";String t = "abc";System.out.println(maxSubSeqNum(s,t));}