LeetCode 131 Palindrome Partitioning

​​LeetCode 131 Palindrome Partitioning​​

划分字符串，得到每一个子串都是回文串，输出所有的方案。

思路是，先将所有的回文子串都找出来，记录下左右端点。
然后DFS这些子串就可以了。

struct Node
{
    string str;
    int l;
    int r;
    Node(){}
    Node(string str,int l,int r)
    {
        this->str =str;
        this->l =l;
        this->r =r;
    }
}a[100005];
class Solution {
public:
       int tag=0;
    vector<string> res;
    vector<vector<string>> ans;
    vector<vector<string>> partition(string s) {
        
      int l =s.length();
     
     for(int i=1;i<=l;i++)
     {
         for(int j=0;j+i-1<l;j++)
         {
             if(judge(s.substr(j,i)))
                 a[tag++]=Node(s.substr(j,i),j,j+i-1);
         }
     }
        
        dfs(0,l);
        return ans;
        
    }
    
    void dfs(int start,int l)
    {
        if(start == l)
        {
            ans.push_back(res);
            return;
        }
        for(int i=0;i<tag;i++)
        {
            if(a[i].l == start)
            {
                res.push_back(a[i].str);
                dfs(a[i].r+1,l);
                res.pop_back();
            }
        }
    }
    
    bool judge(string s)
    {
        int l = s.length();
        for(int i=0,j=l-1;i<j;i++,j--)
        {
            if(s[i]!=s[j])
                return false;
        }
        return true;
    }
};

【文章原创作者：欧洲服务器 http://www.558idc.com/helan.html 复制请保留原URL】