Commitf505d6f

committed

HARD/src/hard/PalindromePartitioningII.java

1 parent4c6a31f commitf505d6fCopy full SHA for f505d6f

File tree

+31

-0

lines changed

+31

-0

lines changed

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,31 @@`
	`1`	`+packagehard;`
	`2`	`+`
	`3`	`+publicclassPalindromePartitioningII {`
	`4`	`+/*This solution is cooler than Jiuzhang: https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36/`
	`5`	`+`
	`6`	`+//cut[i] stands for the minimum number of cut needed to cut [0, i] into palindromes`
	`7`	`+//we initiazlie cut[i] with its max possible value which is i, this is because a single char is naturally a palindrome, so, we'll cut this string into all single-char substrings, which is the max cuts needed`
	`8`	`+`
	`9`	`+publicintminCut(Strings) {`
	`10`	`+intn =s.length();`
	`11`	`+char[]c =s.toCharArray();`
	`12`	`+boolean[][]dp =newboolean[n][n];`
	`13`	`+int[]cut =newint[n];`
	`14`	`+`
	`15`	`+for(inti =0;i <n;i++){`
	`16`	`+cut[i] =i;`
	`17`	`+for(intj =0;j <=i;j++){`
	`18`	`+if(c[i] ==c[j] && (j+1 >i-1 \|\|dp[j+1][i-1])){`
	`19`	`+dp[j][i] =true;`
	`20`	`+if(j ==0){`
	`21`	`+cut[i] =0;`
	`22`	`+ }else {`
	`23`	`+cut[i] = (cut[i] <cut[j-1]+1) ?cut[i] :cut[j-1]+1;`
	`24`	`+ }`
	`25`	`+ }`
	`26`	`+ }`
	`27`	`+ }`
	`28`	`+`
	`29`	`+returncut[n-1];`
	`30`	`+ }`
	`31`	`+}`

Comments

(0)