前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 131 Palindrome Partitioning

LeetCode 131 Palindrome Partitioning

作者头像
ShenduCC
发布2018-12-07 10:40:13
3190
发布2018-12-07 10:40:13
举报
文章被收录于专栏:算法修养算法修养算法修养

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;
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-11-07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档