专栏首页算法修养LeetCode 132 Palindrome Partitioning II

LeetCode 132 Palindrome Partitioning II

LeetCode 132 Palindrome Partitioning II

思路,和上一题一样,先将所有回文串取出。

然后用BFS,找到最小的切割数就可以。

因为没有要求输出字符串,所以结构体中的string 属性可以去掉,防止内存超限。

c++

struct Node
{
    int l;
    int r;
    Node(){}
    Node(int l,int r)
    {
        this->l =l;
        this->r =r;
    }
}a[1000005];
class Solution {
public:
    int tag=0;
    int vis[100005];
  
    int minCut(string s) {
  
        int l =s.length();
    
        for(int i=0;i<l;i++)
        {
            vis[i]=999999;
        }
      
        for(int i=l;i>=1;i--)
        {
            for(int j=0;j+i-1<l;j++)
            {      
                if(judge(s.substr(j,i)))
                {
                    a[tag++]=Node(j,j+i-1);
                }
            }
        }
        
        queue<pair<Node,int>> q;
        for(int i=0;i<tag;i++)
        {
             if(a[i].l==0)
             {
                 q.push(make_pair(a[i],1));
                 vis[a[i].r] = min(vis[a[i].r],1);
             }
        }
        while(!q.empty())
        {
            pair<Node,int> term =q.front();
            q.pop();
            if(term.first.r == l-1)
                return term.second-1;
            for(int i=0;i<tag;i++)
            {
                if(a[i].l==term.first.r+1)
                {
                    if(vis[a[i].r]>term.second+1){
                        q.push(make_pair(a[i],term.second+1));
                        vis[a[i].r] = term.second+1;
                    }
                    
                }
            }
        }
    }
   
    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;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 周赛 184

    判断字符串是不是子串,效率高的方式应该是字典树,按照字典序排序后,建树,再建的过程中就可以得到答案。 但是这是比赛中,又是第一题,所以直接用contains了

    ShenduCC
  • CodeForces #549 Div.2 ELynyrd Skynyrd

    对于每个区间,我们从右边边界,往左边走,如果能走n-1次,那说明以右边边界为起点存在一个题目中说的子链。

    ShenduCC
  • HDU 1403 Eight&POJ 1077(康拖,A* ,BFS,双广)

    Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Ja...

    ShenduCC
  • 2491 玉蟾宫

    2491 玉蟾宫 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 大师 Master 题目描述 Description   有一天...

    attack
  • P1021 邮票面值设计

    题目描述 给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤15)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,...

    attack
  • 车站分级 拓扑排序

    用户2965768
  • LeetCode 周赛 184

    判断字符串是不是子串,效率高的方式应该是字典树,按照字典序排序后,建树,再建的过程中就可以得到答案。 但是这是比赛中,又是第一题,所以直接用contains了

    ShenduCC
  • Day3上午解题报告

    预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

    attack
  • 2017.7.21夏令营清北学堂解题报告

    预计分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标 一句话总结:今天该买彩票! T1: 题目描述 从前有一个?...

    attack
  • 【POJ 1062】昂贵的聘礼(最短路)

    饶文津

扫码关注云+社区

领取腾讯云代金券