# Local success but online runtime error

• the algorithm is quite easy:
DP first: O(nn)
BFS second: O(n)
whole time complexity is O(n
n)
code is as below, works well on my local but runtime error online:

``````#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

class Solution{
public:
void test(){
cout<<minCut("ababbbabbaba")<<endl;
}
int minCut(string s){
bool** record=new bool*[s.size()];
for(unsigned int i=0;i<s.size();i++){
record[i]=new bool[s.size()];
memset(record[i],false,sizeof(bool)*s.size());
}
int n=s.size();
for(int i=0;i<n;i++)
record[i][i]=true;
for(int i=0;i<n-1;i++)
record[i][i+1]=(s[i]==s[i+1]);
for(int i=2;i<n-1;i++){
for(int j=0;j+i<n;j++){
int left=j;
int right=j+i;
record[left][right]=(s[left]==s[right]) && record[left+1][right-1];
}
}
vector<int>* jumps=new vector<int>[n];
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
if(record[i][j])
jumps[i].push_back(j+1);
}
}
for(int i=0;i<n;i++){
delete[] record[i];
}
delete[] record;
int result=getMinjump(jumps,n);
delete[] jumps;
return result;
}
int getMinjump(vector<int>* jumps, int n){
int level=0;
bool* visited=new bool[n];
memset(visited,false,sizeof(bool)*n);
queue<pair<int,int> >Q;
Q.push(make_pair(0,level));
visited[0]=true;
while(!Q.empty()){
pair<int,int> tmp=Q.front();
Q.pop();
if(tmp.first==n){
delete[] visited;
return tmp.second-1;
}
for(unsigned int i=0;i<jumps[tmp.first].size();i++){
if(!visited[jumps[tmp.first][i]]){
Q.push(make_pair(jumps[tmp.first][i],tmp.second+1));
visited[jumps[tmp.first][i]]=true;
}
}
}
return -1;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.