Commit2e5ad96

committed

Create 2707-extra-characters-in-a-string.java

1 parent06d008c commit2e5ad96Copy full SHA for 2e5ad96

File tree

+26

-0

lines changed

+26

-0

lines changed

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+/*`
	`2`	`+ Let N = length of string s, M = length of dictionary`
	`3`	`+ Time: O(N * M)`
	`4`	`+ Space: O(N)`
	`5`	`+*/`
	`6`	`+classSolution {`
	`7`	`+publicintminExtraChar(Strings,String[]dictionary) {`
	`8`	`+intn =s.length();`
	`9`	`+int[]dp =newint[n+1];`
	`10`	`+`
	`11`	`+Arrays.fill(dp,n);`
	`12`	`+dp[0] =0;`
	`13`	`+`
	`14`	`+for (inti =1;i <=n; ++i) {`
	`15`	`+for (intj =0;j <dictionary.length; ++j) {`
	`16`	`+intlen =dictionary[j].length();`
	`17`	`+if (i >=len &&s.substring(i -len,i).equals(dictionary[j])) {`
	`18`	`+dp[i] =Math.min(dp[i],dp[i -len]);`
	`19`	`+ }`
	`20`	`+ }`
	`21`	`+dp[i] =Math.min(dp[i],dp[i -1] +1);`
	`22`	`+ }`
	`23`	`+`
	`24`	`+returndp[n];`
	`25`	`+ }`
	`26`	`+}`

Comments

(0)