[LeetCode]Distinct Subsequences

dp经典题

题目

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).

Example S> = “rabbbit”, T = “rabbit”

Return 3.

解题思路解法一：依次遍历两个字符串，直到T遍历结束，视为找到一个子串，这个就不用实现了解法二：使用迭代思想，res表示T的第一个字符开始的子串能够找到子序列个数。将T的第一个字符依次和S中的字符比较，如果相同，则计算T的下一位子串和S的下一位子串，结果累加如res中。 解法一和解法二都存在重复计算问题，，思路简单，但是大数据量时无法求解。

解法三：dp思想。

如果T[i] == S[j]则 dp[i][j] = dp[i][j + 1] + dp[i + 1][j + 1]如果T[i] != S[j]则 dp[i][j] = dp[i][j + 1]公式简单，程序更简单

解法四：类似于dp思想。数组dp[][] 第一维度表示T中第i个字符，第二维度表示上一个字符在S中开始找的位置，值表示T第i个可以在S第j位开始满足子串查找的个数。 写程序的时候感觉还行，现在想想感觉这个思路还是有点绕，用公式来理解的话比dp思路麻烦多了

程序解法二{/*** @param S, T: Two string.* @return: Count the number of distinct subsequences*/(String S, String T) {int res = 0;if(T.length() == 0 || S.length()<T.length() )return res;char k = T.charAt(0);if(T.length() == 1){for(int i=0;i<S.length();i++){if(k == S.charAt(i))res = res + 1;}return res;} else {for(int i=0;i<=S.length()-T.length();i++){if(k == S.charAt(i))res = res + numDistinct(S.substring(i+1),T.substring(1));}return res;}}}解法三{/*** @param S, T: Two string.* @return: Count the number of distinct subsequences*/(String S, String T) {if (T.length() == 0 || S.length() < T.length())return 0;int[][] dp = new int[T.length() + 1][S.length() + 1];Arrays.fill(dp[T.length()], 1);for (int i = T.length() – 1; i >= 0; i–) {for (int j = S.length() + i – T.length(); j >= 0; j–) {if (S.charAt(j) == T.charAt(i))dp[i][j] = dp[i][j + 1] + dp[i + 1][j + 1];elsedp[i][j] = dp[i][j + 1];}}return dp[0][0];}}解法四{/*** @param S, T: Two string.* @return: Count the number of distinct subsequences*/(String S, String T) {int res = 0;if (T.length() == 0 || S.length() < T.length())return res;int[][] dp = new int[T.length()][S.length()];for (int i = T.length() – 1; i >= 0; i–) {for (int j = S.length() – 1; j >= 0; j–) {if (i == T.length() – 1) {if (S.charAt(j) == T.charAt(i))dp[i][j] = 1;} else {if (S.charAt(j) == T.charAt(i)) {int s = 0;for (int k = j + 1; k < S.length(); k++)s = s + dp[i + 1][k];dp[i][j] = s;}}}}int s = 0;for (int i = 0; i < S.length(); i++)s = s + dp[0][i];return s;}}

赶快上路吧，不要有一天我们在对方的葬礼上说，要是当时去了就好了。