Linear time constant space solution for Longest Valid Parentheses


  • 1
    C

    This problem has only two cases, insufficient ( or insufficient ). Hence, I get a linear time constant space solution.

    class Solution {
    public:
        // my unique solution
        // take care of the case "()(()"
        // can also maitain the position of the left "("
        int longestValidParentheses(string s) {
            int result1 = 0, result2 = 0;
            int r = 0;
            int mystack = 0;
            for(int i=0; i<s.size(); i++){
                if(s[i]=='(')
                    mystack++;
                else{
                    if(mystack==0)  // reset and restart
                        r = 0;
                    else{ // a pair of well-formed parentheses is found
                        mystack--;
                        r += 2;
                        if(mystack==0&&r>result1)
                            result1 = r;
                    }
                }
            }
            r = 0;
            mystack = 0;
            for(int i=s.size()-1; i>=0; i--){
                if(s[i]==')') // the key
                    mystack++;
                else{
                    if(mystack==0)  // reset and restart
                        r = 0;
                    else{ // a pair of well-formed parentheses is found
                        mystack--;
                        r += 2;
                        if(mystack==0&&r>result2)
                            result2 = r;
                    }
                }
            }
            return result1>result2?result1:result2;
        }
    };

  • 0
    Z

    s[i]? s is a string, not an array, u mean s.toCharArray()?


  • 0
    C

    s is a string, s[i] is the (i+1)-th character in the string. The data type of string can be used in a manner that is similar to an array.


Log in to reply
 

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