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;
    }
};