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