How can I optimize my code to avoid "time limit exceed"?


  • 0
    Y
    int minCut(string s) {
        if (s.length() <= 1) return 0;
        
        int len = s.length();
        vector<vector<int>> PP (len, vector<int>(len, 0));
        
        for (int start = len-2; start >= 0; start --){
            int end = start + 1;
            PP[start][end] = s[start] == s[end] ? 0 : 1;
            
            for (int end = start+2; end < len; end ++){
                if (s[start] == s[end] && PP[start+1][end-1] == 0){ // palindrome
                    PP[start][end] = 0;
                }
                else {
                    int min = 0;
                    for (int i=0; i<end-start; i++){
                        int numCut = PP[start][start+i] + PP[start+i+1][end] + 1;
                        min = min < numCut ? min : numCut;
                    }
                    PP[start][end] = min;
                }
            }
        }
        
        return PP[0][len-1];
    }

Log in to reply
 

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