My code pass all cases locally but fail on line


  • 0
    W

    The code compiled locally output is different from leetcode:

    This is the case leetcode beat me:
    Input: "())(())(()(((((())()())()())()((()(((()()))())(((()()(((())())))()()))))(()))))))(((((((())))(())(())(()()((()))))))()((())))))(())))))("
    Output: 80
    Expected: 76

    When I compile with gcc on my mac the output is 76!
    Why this can happen;

    int longestValidParentheses(string s) {
            int n = s.size();
            vector<int> dp(n, 0);
            int i,j;
            int max = 0;
            for(i = 0; i < n; i++) {
                if(s[i] == '(') {
                    dp[i] = 0;
                } else {
                    if(i - 1 >= 0 && s[i-1] == '(') {
                        dp[i] = 2;
                        if(i - 2 >= 0 && dp[i-2] > 0) {
                            dp[i] += dp[i-2];
                        }
                    } else if(i - 1 >= 0 && dp[i-1] > 0 && s[i-1-dp[i-1]] == '(') {
                        dp[i] = dp[i-1] + 2;
                        if(i-2-dp[i-1] >= 0 && dp[i-2-dp[i-1]] > 0) {
                            dp[i] += dp[i-2-dp[i-1]];
                        }
                    }
                    if(dp[i] > max) {
                        max = dp[i];
                    }
                }
            }
            return max;
        }
    

    This is the test code :

    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
        int longestValidParentheses(string s) {
            int n = s.size();
            vector<int> dp(n, 0);
            int i,j;
            int max = 0;
            for(i = 0; i < n; i++) {
                if(s[i] == '(') {
                    dp[i] = 0;
                } else {
                    if(i - 1 >= 0 && s[i-1] == '(') {
                        dp[i] = 2;
                        if(i - 2 >= 0 && dp[i-2] > 0) {
                            dp[i] += dp[i-2];
                        }
                    } else if(i - 1 >= 0 && dp[i-1] > 0 && s[i-1-dp[i-1]] == '(') {
                        dp[i] = dp[i-1] + 2;
                        if(i-2-dp[i-1] >= 0 && dp[i-2-dp[i-1]] > 0) {
                            dp[i] += dp[i-2-dp[i-1]];
                        }
                    }
                    if(dp[i] > max) {
                        max = dp[i];
                    }
                }
            }
            return max;
        }
    
    int main()
    {
    	cout << longestValidParentheses("())(())(()(((((())()())()())()((()(((()()))())(((()()(((())())))()()))))(()))))))(((((((())))(())(())(()()((()))))))()((())))))(())))))(") << endl;
        return 0;
    }
    

    The output is 76!???


  • 2
    W

    I don't know why the OJ will give the result to be 80 instead of 76, but I think I have found the fault.

    else if(i - 1 >= 0 && dp[i-1] > 0 && s[i-1-dp[i-1]] == '(') {
    

    Here, you didn't judge whether i-1-dp[i-1] is positive or not and this mistake will cause visiting negative index of string.

    Besides, I have modified your code because a if clause is redundant, and int j.

    The below code have passed OJ for your reference.

    class Solution {
        public:
            int longestValidParentheses(string s) {
                int n = s.size();
                vector<int> dp(n, 0);
                int max = 0;
                for(int i = 0; i < n; ++i) {
                    if(s[i] == ')') {
        				if(i - 1 >= 0 && s[i - 1] == '(') {
        					dp[i] = 2;
                            if(i - 2 >= 0 && dp[i - 2] > 0) {
        						dp[i] += dp[i - 2];
                            }
                        } 
        				else if(i - 1 >= 0 && dp[i - 1] > 0 && i - 1 - dp[i - 1] >= 0 && s[i - 1 - dp[i - 1]] == '(') {
                            dp[i] = dp[i - 1] + 2;
                            if(i - 2 -dp[i - 1] >= 0 && dp[i - 2 - dp[i - 1]] > 0) {
                                dp[i] += dp[i - 2 - dp[i - 1]];
                            }
                        }
                        if(dp[i] > max) {
                            max = dp[i];
                        }
                    }
                }
                return max;
            }
        };

  • 0
    W

    thank you!!!!!!!


Log in to reply
 

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