题解 | #所有的回文子串I#

#include "iostream"
#include "vector"
using namespace std;
//问题描述：农场主人有一群牛，他给每只牛都取了一个名字，名字由小写字母组成。农场主人希望将这些牛分成一些组，
//每组的牛的名字合在一起都是回文串。回文串是正着读和反着读都一样的字符串。请你帮助农场主人找出所有可能的分组方案。每个分组方案按照字典序升序返回。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector<vector<>>
     */
    // 判断是否为回文字符串
    bool check(string str)
    {
        int left = 0;
        int right = str.size()-1;
        while(left<right)
        {
            if(str[left++]!=str[right--])
                return false;
        }

        return true;
    }
    
    vector<string> v;
    vector<vector<string>> ans;
    // 深度优先搜索
    void dfs(string& s, int start)
    {
        if(start>=s.size())
        {
            ans.emplace_back(v);
            return;
        }

        for(int i=start; i<s.size(); ++i)
        {
            // 得到子串
            string str = s.substr(start, i-start+1);
            // 判断该子串是否为回文字符串
            if(check(str))
            {
                v.emplace_back(str);
                // 从子串的下一个位置开始递归
                dfs(s,i+1);
                // 回溯
                v.pop_back();
            }
        }
    }

    vector<vector<string> > partition(string s) {
        // write code here
        dfs(s,0);
        return ans;
    }
};

// class Solution {
// public:
//     //判断字符串str[s,e]区间的子串是否是回文串
//     bool check(string& str,int s,int e)
//     {

//         for(int i=s,j=e;i<j;i++,j--)
//         {
//             if(str[i]!=str[j]) return false;
//         }
//         return true;
//     }

//     vector<vector<string> > ans;
//     vector<string> path;
//     void backtrack(string& s,int start)
//     {
//         if(start>=s.size())
//         {
//             ans.emplace_back(path);
//             return ;
//         }
//         for(int i=start;i<s.size();i++)
//         {
//             //判断子串s[start,i]是否是回文串
//             string sub=s.substr(start,i-start+1);
//             //把以start为起点的所有回文子串找出来加进path中
//             //是，就加入path中
//             if(check(s,start,i)) path.emplace_back(sub);
//             //不是回文串，就增加子串长度
//             else continue;
//             //递归，以start为起点的回文子串找完后就从新的起点开始找
//             backtrack(s,i+1);
//             //回溯
//             path.pop_back();
//         }
//     }
//     vector<vector<string> > partition(string s)
//     {
//         backtrack(s,0);
//         return ans;
//     }
// };