Commit82067f3

committed

HARD/src/hard/DistinctSubsequences.java

1 parentb2b872f commit82067f3Copy full SHA for 82067f3

File tree

+34

-0

lines changed

+34

-0

lines changed

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,34 @@`
	`1`	`+packagehard;`
	`2`	`+`
	`3`	`+publicclassDistinctSubsequences {`
	`4`	`+/**This is a typical DP problem, illustrated in Jiuzhang.`
	`5`	`+ *`
	`6`	`+ * I've drawn out the 2d matrix on the whiteboard:`
	`7`	`+ *`
	`8`	`+ * 1. initialize a 2d matrix of size (m+1)*(n+1)`
	`9`	`+ * 2. initialize row 0, it should be 1,0,0,0,0... this is because when S is an empty string, only when T is empty, it could be a subsequence`
	`10`	`+ * 3. initialize column 0, it should be 1,1,1,1,1,1...`
	`11`	`+ * 4. starting from (1,1)*/`
	`12`	`+`
	`13`	`+publicintnumDistinct(Strings,Stringt) {`
	`14`	`+intm =s.length(),n =t.length();`
	`15`	`+int[][]dp =newint[m+1][n+1];`
	`16`	`+`
	`17`	`+char[]schar =s.toCharArray();`
	`18`	`+char[]tchar =t.toCharArray();`
	`19`	`+`
	`20`	`+for(inti =0;i <=m;i++)dp[i][0] =1;`
	`21`	`+`
	`22`	`+for(intj =1;j <=n;j++)dp[0][j] =0;`
	`23`	`+`
	`24`	`+for(inti =1;i <=m;i++){`
	`25`	`+for(intj =1;j <=n;j++){`
	`26`	`+if(schar[i-1] ==tchar[j-1])dp[i][j] =dp[i-1][j]+dp[i-1][j-1];`
	`27`	`+elsedp[i][j] =dp[i-1][j];`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+`
	`31`	`+returndp[m][n];`
	`32`	`+ }`
	`33`	`+`
	`34`	`+}`

Comments

(0)