力扣131分隔回文串

文章目录

力扣131分隔回文串
- 题目链接
- 题目描述
- AC代码--暴搜+剪枝
- 暴搜+剪枝思路
- AC代码--预处理+暴搜
- 预处理+暴搜思路

力扣131分隔回文串

题目链接

原题链接

题目描述

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

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：

输入：s = “a”
输出：[[“a”]]

AC代码–暴搜+剪枝

class Solution {
public:
    vector<vector<string>> res; //所有方案
    vector<string> path; //一个合法方案
    vector<vector<string>> partition(string s) {
        dfs(0, s); //从位置0开始dfs
        return res;
    }

    void dfs(int u, string s)
    {
        if (u == s.size()) //遍历完整个字符串
        {
            res.push_back(path); //将路径加入方案
            return;
        }

        for (int i = u; i < s.size(); i ++) //枚举从当前字符到结尾可以选择的长度
        {
            if (check(s, u, i)) //判断u ~ i是否为回文串
            {
                path.push_back(s.substr(u, i - u + 1)); //加入路径
                dfs(i + 1, s); //递归下一层
                path.pop_back(); //回溯
            }
        }
    }

    bool check(string s, int l, int r) //判断从l到r是否为回文串
    {
        while (l <= r)
        {
            if (s[l ++] != s[r --])
                return false;
        }

        return true;
    }
};

暴搜+剪枝思路

见注释

AC代码–预处理+暴搜

class Solution {
public:
    vector<string> path;
    vector<vector<string>> ans;
    vector<vector<bool>> f;
    vector<vector<string>> partition(string s) {
        int n = s.size();
        f = vector<vector<bool>>(n, vector<bool>(n));
        for (int j = 0; j < n; j ++ )
            for (int i = 0; i <= j; i ++ )
                if (i == j) f[i][j] = true;
                else if (s[i] == s[j])
                {
                    if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;
                }

        dfs(s, 0);
        return ans;
    }

    void dfs(string& s, int u)
    {
        if (u == s.size()) ans.push_back(path);
        else
        {
            for (int i = u; i < s.size(); i ++ )
            {
                if (f[u][i])
                {
                    path.push_back(s.substr(u, i - u + 1));
                    dfs(s, i + 1);
                    path.pop_back();
                }
            }
        }
    }
};