Commit3f39570

committed

MEDIUM/src/medium/WordBreak.java

1 parent82067f3 commit3f39570Copy full SHA for 3f39570

File tree

+10

-3

lines changed

+10

-3

lines changed

Lines changed: 10 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -5,21 +5,28 @@`
`5`	`5`	`publicclassWordBreak {`
`6`	`6`
`7`	`7`	`//Jiuzhang gives a very good illustration for this problem!`
	`8`	`+`
`8`	`9`	`publicbooleanwordBreak(Strings,Set<String>wordDict) {`
	`10`	`+intmaxLen =Integer.MIN_VALUE;`
	`11`	`+for(Stringword :wordDict){`
	`12`	`+maxLen = (word.length() >maxLen) ?word.length() :maxLen;`
	`13`	`+ }`
	`14`	`+`
`9`	`15`	`intn =s.length();`
`10`	`16`	`boolean[]dp =newboolean[n+1];`
`11`	`17`	`dp[0] =true;`
`12`	`18`	`for(inti =1;i <=n;i++){`
`13`		`-for(intj =0;j <i;j++){`
`14`		`-if(!dp[j])continue;`
	`19`	`+for(intj =1;j <=i &&j <=maxLen;j++){`
	`20`	`+if(!dp[i-j])continue;`
`15`	`21`
`16`		`-Stringsub =s.substring(j,i);`
	`22`	`+Stringsub =s.substring(i-j,i);`
`17`	`23`	`if(wordDict.contains(sub)){`
`18`	`24`	`dp[i] =true;`
`19`	`25`	`break;`
`20`	`26`	`}`
`21`	`27`	`}`
`22`	`28`	`}`
	`29`	`+`
`23`	`30`	`returndp[n];`
`24`	`31`	`}`
`25`	`32`

Comments

(0)