132. 分割回文串 II
题目
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: “aab” 输出: 1 解释: 进行一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
思路
和完全平方数这个思路很像
代码
public boolean check(String t
){
int n
= t
.length();
for(int i
=0;i
<n
/2;i
++){
if(t
.charAt(i
)==t
.charAt(n
-i
-1)){
continue;
}else{
return false;
}
}
return true;
}
public int minCut(String s
) {
int n
= s
.length();
int f
[] = new int[n
+1];
f
[0] = 0;
for(int i
=1;i
<=n
;i
++){
if(i
==1){
f
[i
]= 1;
}else{
f
[i
] = i
;
for(int j
=1;j
<=i
;j
++){
if(check(s
.substring(j
-1,i
))){
f
[i
] = Math
.min(f
[i
],f
[j
-1]+1);
}
}
}
}
return f
[n
]-1;
}
优化
这里判断是否是回文的函数时间复杂度是O(n)的，因此总的时间复杂度是O(n^3)的，比较慢，可以进一步优化。
