leetcode 131.分割回文串
程序员文章站
2022-07-01 17:10:11
...
原题
题解
方法一 暴力回溯
用一个移动的指针来作为每一个回溯周期的起始点,直到指针跳到字符串之外结束。终止条件是遇到子串不是回文。
本思路java代码示例:
/*
@v7fgg
执行用时:4 ms, 在所有 Java 提交中击败了49.07%的用户
内存消耗:40.4 MB, 在所有 Java 提交中击败了89.60%的用户
2020年8月1日 11:39
*/
class Solution {
List<List<String>> ans=new ArrayList<>();
public List<List<String>> partition(String s) {
fenge(s,0,new ArrayList<>());
return ans;
}
public void fenge(String s,int kaishi,List<String> list){
if(kaishi==s.length()){
ans.add(new ArrayList<>(list));
return;
}
for(int i=kaishi+1;i<=s.length();i++){
String str=s.substring(kaishi,i);
if(huiwen(str)){
list.add(str);
fenge(s,i,list);
list.remove(list.size()-1);
}
}
}
public boolean huiwen(String str){
for(int i=0;i<str.length();i++){
if(str.charAt(i)!=str.charAt(str.length()-1-i)){
return false;
}
}
return true;
}
}
方法二 dp+回溯
和方法一的回溯不同的是,用一个二维数组来代表回文判断((i,j)代表的是从i到j截取的子串是回文串)。
本思路java代码示例:
/*
@v7fgg
执行用时:3 ms, 在所有 Java 提交中击败了69.45%的用户
内存消耗:40.8 MB, 在所有 Java 提交中击败了46.82%的用户
2020年8月1日 16:34
*/
class Solution {
List<List<String>> ans;
public List<List<String>> partition(String s) {
ans=new ArrayList<>();
//表示从i到j是否为回文串
boolean huiwenchuan[][]=new boolean[s.length()][s.length()];
for(int i=0;i<s.length();i++){
huiwenchuan[i][i]=true;
if(i<s.length()-1){
huiwenchuan[i][i+1]=s.charAt(i)==s.charAt(i+1);
}
}
//需要自左下到右上更新
for(int sum=2;sum<=2*s.length()-4;sum++){
for(int i=sum/2-1;i>=0&&sum-i<s.length();i--){
huiwenchuan[i][sum-i]=huiwenchuan[i+1][sum-i-1]&&s.charAt(i)==s.charAt(sum-i);
}
}
fenge(s,0,huiwenchuan,new ArrayList<>());
return ans;
}
public void fenge(String s,int kaishi,boolean[][] huiwenchuan,List<String> list){
if(kaishi==s.length()){
ans.add(new ArrayList<>(list));
return;
}
for(int i=kaishi+1;i<=s.length();i++){
if(huiwenchuan[kaishi][i-1]){
list.add(s.substring(kaishi,i));
fenge(s,i,huiwenchuan,list);
list.remove(list.size()-1);
}
}
}
}
上一篇: 转载:浅谈Java的输入输出流 JAVA文件Reader输入输出
下一篇: 网络基础-网络协议