Commit29fcdd2

applewjg

committed

DistinctSubsequences

Change-Id: I9449c7046cc986d5ef7cc0830906016819743535

1 parent34f62ea commit29fcdd2Copy full SHA for 29fcdd2

File tree

+33

-0

lines changed

+33

-0

lines changed

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,33 @@`
	`1`	`+/*`
	`2`	`+ Author: Andy, nkuwjg@gmail.com`
	`3`	`+ Date: Oct 07, 2014`
	`4`	`+ Problem: Distinct Subsequences`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/distinct-subsequences/`
	`7`	`+ Notes:`
	`8`	`+ Given a string S and a string T, count the number of distinct subsequences of T in S.`
	`9`	`+ A subsequence of a string is a new string which is formed from the original string by deleting`
	`10`	`+ 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).`
	`11`	`+`
	`12`	`+ Here is an example:`
	`13`	`+ S = "rabbbit", T = "rabbit"`
	`14`	`+ Return 3.`
	`15`	`+`
	`16`	`+ Solution: dp.`
	`17`	`+ */`
	`18`	`+`
	`19`	`+publicclassSolution {`
	`20`	`+publicintnumDistinct(StringS,StringT) {`
	`21`	`+intM =S.length();`
	`22`	`+intN =T.length();`
	`23`	`+int[]dp =newint[N+1];`
	`24`	`+Arrays.fill(dp,0);`
	`25`	`+dp[0] =1;`
	`26`	`+for (inti =1;i <=M; ++i) {`
	`27`	`+for (intj =N;j >=1; --j) {`
	`28`	`+dp[j] =dp[j] + (S.charAt(i-1) ==T.charAt(j-1) ?dp[j-1] :0);`
	`29`	`+ }`
	`30`	`+ }`
	`31`	`+returndp[N];`
	`32`	`+ }`
	`33`	`+}`

Comments

(0)