首页 > 代码库 > [leetcode]Distinct Subsequences
[leetcode]Distinct Subsequences
Distinct Subsequences
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.
算法思路：
思路1：递归，求出所有长度为t.length()的子串，相比会超时
思路2：DP；dp[i][j]代表从s[0..i]中删除s.length - t.length个字符得到t[0..j]的不同删除方法数。
- 初始化：如果t为空，任意的s删除到t都是1种。
- 如果S[i] = T[j], dp[i][j] = dp[i-1][j-1]+dp[i][j - 1]
- 如果S[i] 不等于 T[j], dp[i][j] = dp[i][j - 1]
代码如下：
1 public class Solution { 2 public int numDistinct(String s, String t) { 3 if(s == null || t == null || s.length() < t.length()) return 0; 4 int[][] dp = new int[t.length() + 1][s.length() + 1]; 5 for(int i = 0; i < s.length() + 1; i++){ 6 dp[0][i] = 1; 7 } 8 for(int i = 1; i < t.length() + 1;i++){ 9 char c = t.charAt(i - 1);10 for(int j = 1; j < s.length() + 1; j++){11 if(s.charAt(j - 1) == c){12 dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];13 }else{14 dp[i][j] = dp[i][j - 1];15 }16 }17 }18 return dp[t.length()][s.length()];19 }20 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。