Commitbddcebe

committed

HARD/src/hard/InterleavingString.java

1 parent887025a commitbddcebeCopy full SHA for bddcebe

File tree

+44

-0

lines changed

+44

-0

lines changed

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,44 @@`
	`1`	`+packagehard;`
	`2`	`+`
	`3`	`+publicclassInterleavingString {`
	`4`	`+publicbooleanisInterleave(Strings1,Strings2,Strings3) {`
	`5`	`+// write your code here`
	`6`	`+intm =s1.length(),n =s2.length();`
	`7`	`+if(m+n !=s3.length())returnfalse;`
	`8`	`+`
	`9`	`+boolean[][]dp =newboolean[m+1][n+1];`
	`10`	`+`
	`11`	`+dp[0][0] =true;`
	`12`	`+`
	`13`	`+for(inti =0;i <m;i++){`
	`14`	`+if(s1.charAt(i) ==s3.charAt(i)){`
	`15`	`+dp[i+1][0] =true;`
	`16`	`+ }`
	`17`	`+else {//if one char fails, that means it breaks, the rest of the chars won't matter any more.`
	`18`	`+//Mian and I found one missing test case on Lintcode: ["b", "aabccc", "aabbbcb"]`
	`19`	`+//if we don't break, here, Lintcode could still accept this code, but Leetcode fails it.`
	`20`	`+`
	`21`	`+break;`
	`22`	`+ }`
	`23`	`+ }`
	`24`	`+`
	`25`	`+for(intj =0;j <n;j++){`
	`26`	`+if(s2.charAt(j) ==s3.charAt(j)){`
	`27`	`+dp[0][j+1] =true;`
	`28`	`+ }`
	`29`	`+else {`
	`30`	`+break;`
	`31`	`+ }`
	`32`	`+ }`
	`33`	`+`
	`34`	`+for(inti =1;i <=m;i++){`
	`35`	`+for(intj =1;j <=n;j++){`
	`36`	`+intk =i+j-1;`
	`37`	`+dp[i][j] = (s1.charAt(i-1) ==s3.charAt(k) &&dp[i-1][j])`
	`38`	`+ \|\| (s2.charAt(j-1) ==s3.charAt(k) &&dp[i][j-1]);`
	`39`	`+ }`
	`40`	`+ }`
	`41`	`+`
	`42`	`+returndp[m][n];`
	`43`	`+ }`
	`44`	`+}`

Comments

(0)