欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 131.分割回文串

程序员文章站 2022-07-01 17:10:11
...

原题

131.分割回文串
leetcode 131.分割回文串

题解

方法一 暴力回溯

用一个移动的指针来作为每一个回溯周期的起始点,直到指针跳到字符串之外结束。终止条件是遇到子串不是回文。
本思路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);
            }
        }
    }
}