leetcode131. 分割回文串，双指针+DFS

leetcode131. 分割回文串

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

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

示例 2：
输入：s = “a”
输出：[[“a”]]

思维导图

题目解析

题目要求我们对于一个给定的字符串s，找出所有可能的分割方案，使得每个子串都是回文串。

算法分析

这个问题可以通过深度优先搜索（DFS）来解决。我们需要检查字符串s的所有子串，判断它们是否是回文串。如果是，我们就将其加入到当前的分割方案中，并继续搜索剩余的字符串。当搜索到字符串末尾时，我们就找到了一个有效的分割方案。

算法步骤

1. 定义一个辅助函数huiwen来判断一个字符串是否是回文。
2. 使用深度优先搜索（DFS）遍历所有可能的分割方式。
3. 对于每个分割点，如果它和起始点之间的子串是回文，就将其加入到当前的分割方案中，并递归搜索剩余的字符串。
4. 当搜索到字符串末尾时，将当前的分割方案加入到结果中。
5. 回溯并继续搜索其他可能的分割方式。

流程图

具体代码

class Solution {
public:
    bool huiwen(string t,int l,int r)
    {
       int i=l;
       int j=r;
       while(i<=j)
       {
           if(t[i]!=t[j]) return false;
           i++;
           j--;
       }
       return true;
    }
    void dfs(string s,int n,vector<vector<string>>& res,vector<string> &path)
    {
        if(n>=s.size())
        {
            res.push_back(path);
            return ;
        }
        for(int i=n;i<s.size();i++)
        {
            if(huiwen(s,n,i))
            {
                string temp=s.substr(n,i-n+1);
                path.push_back(temp);
            }
            else
            {
                continue;
            }
            dfs(s,i+1,res,path);
            path.pop_back();
        }
        return ;
    }
    vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    vector<string> path;
    dfs(s,0,res,path);
    return res;
    }
};

复杂度分析

• 时间复杂度: O(2^n)，其中n是字符串的长度。这是因为对于字符串的每个位置，我们都有两种选择：分割或不分割。
• 空间复杂度: O(n)，用于存储分割方案和递归栈。

易错点

• 在DFS中，确保在回溯之前将当前分割的字符串从路径中移除。
• 正确处理字符串的子串提取，避免越界。

相似题目

• 看这题好像能用dp写，等我刷完dp后再来看看。