文档章节

131. Palindrome Partitioning

cofama
 cofama
发布于 2017/05/04 15:20
字数 1213
阅读 24
收藏 0

原题链接

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

题目的意思是给定一个字符串,找出这个字符串的所有分割方法,要求分割出来的子串都是回文。例如“aab”有a、a、b和aa、b两种分割方法。

正向思维是,从第一个字符开始遍历,如果发现从第一个到第i个字符形成回文,就用substr方法提取出子串,把子串加入到用来表示分割组合的vector中。然后继续从第i+1个字符开始找回文,如此重复,直到字符串末尾,这样就找到了一种分割组合。但题目的要求是找出所有分割组合,例如“aabb”这个字符串,首先会找到a、a、b、b这个分割,如果想找到aa、b、b该怎么做?方法是在找到第1个到第i个的回文后不要停下来,继续找找看有没有第j个字符也形成回文(j>i),当然也要从j+1开始找回文,直到遍历到字符串末尾。而从第i+1个字符开始找回文的过程其实和从第一个字符开始是一样的,只是起点不同,所以可以用递归处理。我判断字符串是否为回文的方法比较简单,就是比较头、尾是否相等,如果相等,就把头加一、尾减一再比较,直到头尾相遇。如果这个过程中出现头尾不等,就不是回文了。

想象一下这个过程,例如对字符串"aabb",我找到了“aa”这个回文,接下来从第一个b开始找回文。由于用的是递归处理,所以在找完以第一个b开头的回文之后,才会回去找以第一个a开头的回文。然后我找到了[aa,b,b]这个分割,之所以会认为这是一个符合要求的分割,是因为找到从某个字符开始到字符串末尾是回文(这个例子中是“b”)。现在第2个b开头的回文找完了,我要回去第一个b找,接着会找到“bb”,把“bb”加入到分组中,结果变成了[aa,b,b,bb]。错误在于没有把第二个b开头的回文从组合中删掉,所以在找完每一个字符开头的回文后,都要把它从组合中删掉,这也是backtracking的精髓所在。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> v;
        vector<string> part;
        findPartition(s, 0, v, part);
        return v;
    }

private:
    void findPartition(string &s, int start, vector<vector<string>> &v, vector<string> &part) {
        for(int i=start; i<s.length(); i++) {
            if(i==start || isPalindrome(s, start, i)) {
                part.push_back(s.substr(start, i-start+1));
                if(i==s.length()-1) v.push_back(part);
                else findPartition(s, i+1, v, part);
                part.pop_back();
            }
        }
    }
    
    bool isPalindrome(string &s, int start, int end) {
        while(start<=end) {
            if(s[start++]!=s[end--]) return false;
        }
        return true;
    }
};

代码中的part用于记录当前的分割组合,v记录所有分割组合。只有当访问到字符串末尾时,才把part加入v。分析下这个算法的时间复杂度,递归函数findPartition在最坏情况下,T(n)=T(n-1)+T(n-2)+...+T(1),这种情况是字符串中每个字符都一样,所以每遍历一个字符都会调用一次递归。同理T(n+1)=T(n)+T(n-1)+T(n-2)+...+T(1)=2T(n),所以T(n)=2^n。加上isPalindrome的复杂度为O(n),所以整个算法复杂度为O(n*2^n)。

实际上这个算法在判断回文是会重复计算。例如"aabb"这个字符串,在我们找到分组a、a或aa后,都会判断“bb”是否为回文,就要重复调用两次isPalindrome。我们可以用一个数组保留判断结果,每次根据数组的值判断是否为回文,而不用调用isPalindrome。如下面的代码(这个代码不是我写的,原文链接在此):

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length(); i++) {
            for(int j = 0; j <= i; j++) {
                if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
                    dp[j][i] = true;
                }
            }
        }
        helper(res, new ArrayList<>(), dp, s, 0);
        return res;
    }
    
    private void helper(List<List<String>> res, List<String> path, boolean[][] dp, String s, int pos) {
        if(pos == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        
        for(int i = pos; i < s.length(); i++) {
            if(dp[pos][i]) {
                path.add(s.substring(pos,i+1));
                helper(res, path, dp, s, i+1);
                path.remove(path.size()-1);
            }
        }
    }
}

dp[j][i]表示第j个字符到第i个字符的子串是否为回文,其中确定dp[j][i]的值又可以利用dp[j+1][i-1]的结果,用到了动态规划的思想。这样helper的时间复杂度依然为O(2^n),判断回文的复杂度为O(n^2),整体复杂度降到了O(2^n)。

© 著作权归作者所有

共有 人打赏支持
下一篇: 72. Edit Distance
cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
私信 提问
LeetCode 131 Palindrome Partitioning

LeetCode 131 Palindrome Partitioning 划分字符串,得到每一个子串都是回文串,输出所有的方案。 思路是,先将所有的回文子串都找出来,记录下左右端点。 然后DFS这些子串就可以了。...

Shendu.cc
2018/11/07
0
0
[LeetCode] Shortest Palindrome 最短回文串

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this tran......

机器的心脏
2017/12/02
0
0
LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder
2017/09/10
0
0
将字符串划分为回文字符串数组 Palindrome Partitioning

问题: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = , Retur......

叶枫啦啦
2017/09/28
0
0
python之扩展

17.2 非常简单的途径:Jython 和 IronPython 一个简单的java类 public class JythonTest{ public void greeting(){ System.out.println("Hello,world"): } } java编译器编译,例如javac $ja......

潘阔
2015/06/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

泛型就这么简单

前言 从今天开始进入Java基础的复习,可能一个星期会有一篇的<十道简单算法>,我写博文的未必都是正确的~如果有写错的地方请大家多多包涵并指正~ 今天要复习的是泛型,泛型在Java中也是个很...

群星纪元
29分钟前
3
0
大数据提醒你:中国这些古建筑,可能是下一个巴黎圣母院!

大家晚上好,我是今天的提笔人嗅嗅。 巴黎圣母院失火事件让我的心情很沉重,一句无关痛痒的安慰“巴黎不哭”,已经不能表达我对这场文化之殇的惋惜之痛,人类伟大的建筑在一瞬间被毁灭。 世界...

forespider
40分钟前
0
0
mysql函数substring_index的用法

substring_index 按索引字符位进行截取字符串 substring_index(“待截取的字符串”,“截取数据依据的字符”,截取字符的位置N) 第三个参数可正,可负。正数表示索引字符前面的字符串,负数...

echojson
40分钟前
1
0
好程序员web前端分享用CSS和JS打造一个简单的图片编辑器

好程序员web前端分享用CSS和JS打造一个简单的图片编辑器,本文主要是利用CSS的 filter和简单的Jquery代码来实现一个简单的图片编辑器,包括对图片的透明度,黑白,图片亮度等调节。 CSS filt...

好程序员IT
50分钟前
2
0
浅析spring mvc的细节

spring mvc 整体结构 系统监听到请求 -> 通知tomcat -> 根据web.xml 通知相应的拦截器(spring mvc 通常指DispatcherServlet) --> 检查url是否有相匹配的请求实现 --> 拿到请求实现bean的适配...

最爱肉肉
52分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部