131.Palindrome Partitioning

131.Palindrome Partitioning
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 难度：Medium 返回 s 所有可能的分割方案。
示例:
1
输入: "aab"
2
输出:
3
[
4
  ["aa","b"],
5
  ["a","a","b"]
6
]
Copied!
直观解决方法：递归。 因为所有子数组都是回文，所以从第一个开始，找到一个回文后，将剩下的子串找出所有的可能性组合，最后再合并即可。 代码如下:
1
class Solution {
2
public:
3
    vector<vector<string>> partition(string s) {
4
        int n=s.length(),cnt=0;
5
        vector<vector<string>> res;
6
        vector<string> ret;
7
        if (n == 1)
8
        {
9
            ret.push_back(s);
10
            res.push_back(ret);
11
            return res;
12
        }
13
​
14
        vector<vector<string>> tmp;
15
        for(int i=1;i<n;i++)
16
        {
17
            string fir=s.substr(0,i);
18
            if(ispalind(fir))
19
            {
20
                tmp=merge(fir,partition(s.substr(i,n-i)));
21
                res.insert(res.end(),tmp.begin(),tmp.end());
22
            }
23
        }
24
        if(ispalind(s))
25
        {
26
            ret.push_back(s);
27
            res.push_back(ret);
28
        }
29
        return res;
30
        
31
    }
32
    vector<vector<string>> merge(string a, vector<vector<string>>b)
33
    {
34
        vector<vector<string>> res;
35
​
36
        for(int i=0;i<b.size();i++)
37
        {
38
            vector<string>tmp;
39
            tmp.push_back(a);
40
            tmp.insert(tmp.end(),b[i].begin(),b[i].end());
41
            res.push_back(tmp);
42
        }
43
        return res;
44
    }
45
    bool ispalind(string s)
46
    {
47
        int n=s.length();
48
        for(int i=0;i<n/2;i++)
49
            if(s[i]!=s[n-i-1]) return false;
50
        return true;
51
    }
52
};
Copied!
定义了一个函数来判断是否是回文，另一个函数用来将第一个子串和剩下的回文向量合并，最后判断整个字符串是否是回文。
但这样并不高效。因为运算时间比较长。 提交结果的一个比较好的示例如下：
1
class Solution {
2
    vector<vector<string>> res;
3
    
4
    void DFS(string& s, int begin, vector<string>& t){
5
        if(begin>=s.length())
6
            res.push_back(t);
7
        else{
8
            t.push_back("");
9
            for(int end=begin;end<s.length();end++)
10
                if(isParl(s, begin, end)){
11
                    t[t.size()-1] = s.substr(begin, end-begin+1);
12
                    DFS(s, end+1, t);
13
                }
14
            t.pop_back();
15
        }
16
    }
17
    
18
    
19
    bool isParl(string& s, int begin, int end){
20
// 可以用DP存储加速
21
        while(begin<end){
22
            if(s[begin]!=s[end])
23
                return false;
24
            begin++;
25
            end--;
26
        }
27
        return true;
28
    }
29
public:
30
    vector<vector<string>> partition(string s) {
31
        vector<string> t;
32
        DFS(s, 0, t);
33
        return res;
34
    }
35
};
Copied!
采用深度优先搜索DFS，也是递归调用完成。

125.Valid Palindrome

139.Word Break

Last modified 5mo ago

Copy link