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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月21日 15:59
下一篇 2020年5月22日

相关推荐

  • leetcode71-简化路径

    原题 以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..…

    算法 2020年1月23日
    0110
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    0110
  • leetcode232-用栈实现队列

    原题 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – …

    算法 2019年12月13日
    0560
  • leetcode1071-字符串的最大公因子

    原题 对于字符串 S 和 T,只有在 S = T + ... + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。 返回最长字符串 X,要求满足 X 能除尽 …

    算法 2020年3月12日
    0250
  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0170
  • leetcode485-最大连续1的个数

    原题 给定一个二进制数组, 计算其中最大连续1的个数。 示例 1: 输入: [1,1,0,1,1,1] 输出: 3 解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是…

    算法 2019年11月20日
    0130
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    0100
  • leetcode63-不同路径II

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月22日
    0130
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0300
  • leetcode13-罗马数字转整数

    原题 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2…

    算法 2020年4月25日
    0100

发表回复

登录后才能评论