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日

相关推荐

  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • leetcode117-填充每个节点的下一个右侧节点指针II

    原题 给定一个二叉树 struct Node {   int val;   Node *left;   Node *ri…

    2020年1月14日
    0370
  • leetcode135-分发糖果

    原题 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个…

    算法 2020年2月17日
    060
  • leetcode503-下一个更大元素II

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

    算法 2020年2月1日
    090
  • leetcode876-链表的中间结点

    原题 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入: [1,2,3,4,5] 输出: 此列表中的结…

    算法 2020年3月23日
    080
  • leetcode75-颜色分类

    原题 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分…

    算法 2020年4月19日
    0220
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0120
  • leetcode84-柱状图中最大的矩形

    原题 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽…

    2020年1月24日
    0100
  • leetcode32-最长有效括号

    原题 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2…

    算法 2020年6月12日
    0140
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250

发表回复

登录后才能评论