131.palindrome_partitioning.md

To Index

131.Palindrome Partitioning

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 难度：Medium 返回 s 所有可能的分割方案。

示例:

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

直观解决方法：递归。 因为所有子数组都是回文，所以从第一个开始，找到一个回文后，将剩下的子串找出所有的可能性组合，最后再合并即可。 代码如下:

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n=s.length(),cnt=0;
        vector<vector<string>> res;
        vector<string> ret;
        if (n == 1)
        {
            ret.push_back(s);
            res.push_back(ret);
            return res;
        }

        vector<vector<string>> tmp;
        for(int i=1;i<n;i++)
        {
            string fir=s.substr(0,i);
            if(ispalind(fir))
            {
                tmp=merge(fir,partition(s.substr(i,n-i)));
                res.insert(res.end(),tmp.begin(),tmp.end());
            }
        }
        if(ispalind(s))
        {
            ret.push_back(s);
            res.push_back(ret);
        }
        return res;
        
    }
    vector<vector<string>> merge(string a, vector<vector<string>>b)
    {
        vector<vector<string>> res;

        for(int i=0;i<b.size();i++)
        {
            vector<string>tmp;
            tmp.push_back(a);
            tmp.insert(tmp.end(),b[i].begin(),b[i].end());
            res.push_back(tmp);
        }
        return res;
    }
    bool ispalind(string s)
    {
        int n=s.length();
        for(int i=0;i<n/2;i++)
            if(s[i]!=s[n-i-1]) return false;
        return true;
    }
};

定义了一个函数来判断是否是回文，另一个函数用来将第一个子串和剩下的回文向量合并，最后判断整个字符串是否是回文。
但这样并不高效。因为运算时间比较长。 提交结果的一个比较好的示例如下：

class Solution {
    vector<vector<string>> res;
    
    void DFS(string& s, int begin, vector<string>& t){
        if(begin>=s.length())
            res.push_back(t);
        else{
            t.push_back("");
            for(int end=begin;end<s.length();end++)
                if(isParl(s, begin, end)){
                    t[t.size()-1] = s.substr(begin, end-begin+1);
                    DFS(s, end+1, t);
                }
            t.pop_back();
        }
    }
    
    
    bool isParl(string& s, int begin, int end){
// 可以用DP存储加速
        while(begin<end){
            if(s[begin]!=s[end])
                return false;
            begin++;
            end--;
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        vector<string> t;
        DFS(s, 0, t);
        return res;
    }
};

采用深度优先搜索DFS，也是递归调用完成。