【LeetCode】131. 分割回文串

发表于 更新于 分类于 Valine：
本文字数： 86 阅读时长 ≈ 1 分钟

131. 分割回文串

思路

  1. 利用dp动态规划判断所有子集是否为回文串

    1
    2
    3
    4
    5
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<n;j++)
        {
            f[i][j]=(s[i]==s[j])&&f[i+1][j-1];
        }

  2. dfs/回溯遍历所有结果，将正确的结果保存到ret中

拓展

  1. s.substr(pos, n) pos:位置 n:长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:
    vector<vector<int>> f;
    vector<vector<string>> ret;
    vector<string> ans;
    int n;

public:
    void dfs(const string& s, int i) {
        if(i==n)
        {
            ret.push_back(ans);
            return;
        }
        for(int j=i;j<n;j++)
        {
            if(f[i][j])
            {
                ans.push_back(s.substr(i,j-i+1));
                dfs(s,j+1);
                ans.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n, true));
        for(int i=n-1;i>=0;i--)
            for(int j=i+1;j<n;j++)
            {
                f[i][j]=(s[i]==s[j])&&f[i+1][j-1];
            }
            dfs(s,0);
        return ret;
    }
};