FilesExpand file tree

 master

/

DistinctSubsequences_115.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (34 loc) · 1.15 KB

 master

/

DistinctSubsequences_115.java

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (34 loc) · 1.15 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

37

package String;

/**

* 动态规划

* 当T的长度大于S的长度时，S的子序列一定没有T，直接返回0

* dp[i][j]：表示S[i:]的子序列中T[j:]的个数

* dp[i][j]

* s[i]=[j]有两种选择，可以选择匹配也可以不选择匹配 dp[i+1][j+1]+dp[i+1][j]

* s[i]!=[j] dp[i+1][j]

*/

public class DistinctSubsequences_115 {

public int numDistinct(String s, String t) {

int m=s.length(),n=t.length();

if(n>m) return 0;

int[][] dp=new int[m+1][n+1];

//当j为n时，T为空串，是S的子序列，初始化为1，当i为m时，S是空串，初始化为0

for(int i=0;i<=m;i++){

dp[i][n]=1;

}

for(int i=m-1;i>=0;i--){

for(int j=n-1;j>=0;j--){

if(s.charAt(i)==t.charAt(j)){

dp[i][j]=dp[i+1][j+1]+dp[i+1][j];

}else{

dp[i][j]=dp[i+1][j];

}

}

}

return dp[0][0];

}

public static void main(String[] args) {

int i = new DistinctSubsequences_115().numDistinct("rabbbit", "rabbit");

System.out.println(i);

}

}