题目描述:
题目分析:看到是字符串,第一反应是动态规划,看到回文,想到构造反字符串,找看公共子串,但是没想出来怎么写,于是就退而求其次,暴力枚举所有子串的情况,逐个情况判断,那么就搜索(如果填空就for了),先想想能不能抽象成线性搜索,感觉可以,每一个“位置”表示截取的子串的长度,例如对于“aab”,那么21代表截取为“aa”和"b",之后开始建模。
模型抽象:
-
状态量:需要一个sum,表示已经截取的子串的长度之和,用于优化和终止条件。
-
维护区:来一个ArrayList
arr,用来保存我们抽象出来的线性搜索的结果,这里用深度搜索,注意回溯 -
转移:转移的时候要考虑上面两个因素的变化,一共有i中情况,i属于[1,length],不能0,0没有意义且死循环,一定要包括length,字符串本身可以是回文,不然会漏情况。
-
终止条件:sum==length
-
优化:如上,做一个减枝
其他:
(1)如何判断是否为回文?直接判断他的他的反字符串是否相等
AC代码:
class Solution {
List> ans ;
ArrayList arr ;
int length;
String str;
public List> partition(String s) {
ans = new ArrayList<>();
arr = new ArrayList<>();
length = s.length();
str = s;
for(int i =1;i<=length;i++){
arr.add(i);
dfs(i);
arr.remove(arr.size()-1);
}
return ans;
}
boolean ishuiwen(String s1){
String s2 = new StringBuilder(s1).reverse().toString();
if(s1.equals(s2)){
return true;
}
else{
return false;
}
}
void dfs(int sum){
if(sum==length){
int start = 0;
int end = 0 ;
for(int i =0;i());
start = 0;
end = 0 ;
for(int i =0;i
运行结果:
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)