当前位置:   article > 正文

leetcode题解131-分割回文串_给你一个字符串strig,string经由小写字母组成,分割成一些子串

给你一个字符串strig,string经由小写字母组成,分割成一些子串

问题描述

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
  • 1
  • 2

示例 2:

输入:s = "a"
输出:[["a"]]
 
  • 1
  • 2
  • 3

提示:

1 <= s.length <= 16
s 仅由小写英文字母组成
  • 1
  • 2

解题思路:回溯 + 动态规划预处理

由于需要求出字符串 s 的所有分割方案,因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。

假设我们当前搜索到字符串的第 i个字符,且 s[0…i-1] 位置的所有字符已经被分割成若干个回文串,并且分割结果被放入了答案数组 ans 中,那么我们就需要枚举下一个回文串的右边界 j,使得 s[i…j]是一个回文串。

因此,我们可以从 i 开始,从小到大依次枚举 j。对于当前枚举的 j 值,我们使用动态规划的方法判断 s[i…j] 是否为回文串:如果 s[i…j]是回文串,那么就将其加入答案数组 ans 中,并以 j+1 作为新的 i 进行下一层搜索,并在未来的回溯时将 s[i…j]从 ans 中移除。

如果我们已经搜索完了字符串的最后一个字符,那么就找到了一种满足要求的分割方法。

当我们在判断 s[i…j]是否为回文串时,可以使用leetcode题解5-最长回文子串提供的思路。

dp[i][i] = (s[i]==s[j])   abd dp[i][j]				当j-i<=1时
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]      当j-i>1
  • 1
  • 2

实现代码

class Solution {
    public List<List<String>> lists;    //结果集合
    public List<String> list;       //分割的子串的集合
    public int n;                   //字符串长度
    public boolean f [][];          //判断子串是否为回文串
    public String str;              //目标字符串
    public List<List<String>> partition(String s) {
        n=s.length();       
        str=s;
        lists=new ArrayList<>();
        list=new ArrayList<>();
        f=new boolean[n][n];
        char []arrStr=s.toCharArray();
        //填充f数组,判断f[i][j]代表的子串是否是回文子串
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                if((i-j)<=1){
                    if(arrStr[i]==arrStr[j]){
                        f[j][i]=true;
                    }
                }else{
                    if(arrStr[i]==arrStr[j] && f[j+1][i-1]==true){
                        f[j][i]=true;
                    }
                }
            }
        }
        dfs(0);
        return lists;
    }
    public void dfs(int i){
        if(i==n){
            lists.add(new ArrayList<String>(list));
            return ;
        }else{
            //从i开始,从小到大依次枚举j,对于当前枚举的j值,我们使用f数组来判断它是否为回文子串
            for(int j=i;j<n;j++){
                //如果是回文子串,那么我们就把其添加到结果集合中,并且以j+1为i继续新的搜索
                if(f[i][j]==true){
                    list.add(str.substring(i,j+1));
                    dfs(j+1);
                //搜索完成以后,将s[i,j]移出。
                    list.remove(list.size()-1);
                }
            }
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/676785
推荐阅读
相关标签
  

闽ICP备14008679号