首页 > itarticle > [leetcode]distinct subsequences

[leetcode]distinct subsequences

admin 11月 11, 2020 0

题目描述

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.

代码

dp[i][j]表示T[0…j-1]在S[0…i-1]中distinc subsequences的数量，则以S =”rabbbit”,T = “rabbit”为例）：

1
2
3
4
5
6
7
8
 
    r a b b b i t
  1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3

所以状态转移方程为

dp[0][0] = 1; // T和S都是空串.
dp[0][1 … S.length() - 1] = 1; // T是空串，S只有一种子序列匹配。
dp[1 … T.length() - 1][0] = 0; // S是空串，T不是空串，S没有子序列匹配。
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0).1 <= i <= T.length(), 1 <= j <= S.length()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
public class Solution {
    public int (String s, String t) {
        
        
        //     return t.length() == 0 ? 1 : 0;
        // }
        
        // if(t.length() == 0){
        //     return 0;
        // }
        
        int[][] dp = new int[t.length() + 1][s.length() + 1];
        
        dp[0][0] = 1;
        
        for(int j = 1; j <= s.length(); j++){
            dp[0][j] = 1;
        }
        
        for(int i = 1; i <= t.length(); i++){
            dp[i][0] = 0;
        }
        
        for(int i = 1; i <= t.length(); i++){
            for(int j = 1; j <= s.length(); 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[t.length()][s.length()];
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能