Local success but online runtime error


  • 0

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

Log in to reply
 

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