FilesExpand file tree

 master

/

DistinctSubsequences.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

36 lines (33 loc) · 1.07 KB

 master

/

DistinctSubsequences.java

Top

File metadata and controls

• Code
• Blame

36 lines (33 loc) · 1.07 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

/**

* Distinct SubsequencesOct 19 '12 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.

*

* f(i, j) = f(i - 1, j) + S[i] == T[j]? f(i - 1, j - 1) : 0 Where f(i, j) is

* the number of distinct sub-sequence for T[0:j] in S[0:i].

*/

public class DistinctSubsequences {

public int numDistinct(String S, String T) {

int[][] f = new int[S.length() + 1][T.length() + 1];

for (int k = 0; k < S.length(); k++)

f[k][0] = 1;

for (int i = 1; i <= S.length(); i++) {

for (int j = 1; j <= T.length(); j++) {

if (S.charAt(i - 1) == T.charAt(j - 1)) {

f[i][j] += f[i - 1][j] + f[i - 1][j - 1];

} else {

f[i][j] += f[i - 1][j];

}

}

}

return f[S.length()][T.length()];

}

}