Commit5b410c9

committed

min cut.

1 parenta338cf3 commit5b410c9Copy full SHA for 5b410c9

File tree

-0

lines changed

-0

lines changed

Lines changed: 4 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -7,6 +7,8 @@ public int minCut(String s) {`
`7`	`7`	`}`
`8`	`8`
`9`	`9`	`intlen =s.length();`
	`10`	`+`
	`11`	`+// D[i] 的定义: 第i个字符到len - 1个字符的最小切割数。`
`10`	`12`	`int[]D =newint[len];`
`11`	`13`
`12`	`14`	`boolean[][]isPalid =newboolean[len][len];`
`@@ -21,6 +23,8 @@ public int minCut(String s) {`
`21`	`23`	`if (s.charAt(i) ==s.charAt(j) && (j -i <=1 \|\|isPalid[i +1][j -1])) {`
`22`	`24`	`isPalid[i][j] =true;`
`23`	`25`	`if (j ==len -1) {`
	`26`	`+// 这里就是特殊处理的地方了。当整个字符串都是回文的时候，因为没有D[Len]，所以这里直接`
	`27`	`+// 将D[i]置为0，意思就是这时不需要任何的划分。`
`24`	`28`	`D[i] =0;`
`25`	`29`	`}else {`
`26`	`30`	`// 如果前半部分是回文，那么我们可以分解为第一个回文 + 后半部分的最小分割数`

Comments

(0)