leetcode131-分割回文串

原题

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

解法

思想

在字符串中搜索是回文串的子字符串,可以使用dfs。

但判断子字符串是不是回文串的时候,可以下功夫优化,这里不能使用我在leetcode125-验证回文串中用到的方法,因为子字符串之间存在很多个重复的单元。

那么就可以使用动态规划的方法判断子字符串是否为回文串:使用一个二维的dp数组,dp[i][j]代表在字符串中下标i起始,下标j截止的子字符串是否为回文串,根据回文串的判断方法,可以得到状态转移方程dp[i][j] = s.charAt(i)==s.charAt(j) && dp[i+1][j-1]

代码

class Solution {
    boolean[][] dp;
    char[] chars;
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> partition(String s) {
        int length = s.length();
        chars = s.toCharArray();
        dp = new boolean[length][length];
        List<String> list = new ArrayList<>();
        dfs(0,list);
        return ans;
    }
    // 子字符串是否是回文串,使用动态规划判断
    public boolean isPalindrome(int startIndex,int endIndex){
        if(startIndex >= endIndex) return true;
        boolean result = chars[startIndex] == chars[endIndex] && isPalindrome(startIndex+1,endIndex-1);
        dp[startIndex][endIndex] = result;
        return result;
    }
    // 从下标为startIndex处进行dfs搜索
    public void dfs(int startIndex,List<String> list){
        for(int i = startIndex;i<chars.length;i++){
            if(isPalindrome(startIndex,i)){
                List<String> copy = new ArrayList<>(list);
                copy.add(new String(chars,startIndex,i-startIndex+1));
                if(i == chars.length-1) ans.add(copy);
                else dfs(i+1,copy);
            }
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode131-%e5%88%86%e5%89%b2%e5%9b%9e%e6%96%87%e4%b8%b2/

发表回复

登录后才能评论