[How to from Error to AC]clean C++ implementation


  • 2

    my first implementation pass 154 / 229 test cases passed.

    Here is the code.

    the pair recorded the valid pair count util the current position, but It may contain some cases like this

       s = "()(()"  it will return 4 but should return 2. It does contain 2 valid pairs, 
       but it is not consecutive. so we should reset the pair=0 when meet the cut char !
    

    But it is not easy to identify the cut char before scanning all the chars. so Can anyone think of how to solve This problem.

    Original code :

    class Solution {
    public:
        int longestValidParentheses(string s) {
            int pair=0, left=0, right=0;
            int result=0;
            for(int i=0; i<s.size(); i++){
                if(s[i]=='(')  left++;
                else {
                    if(left>0){
                        left--;
                        pair++;
                    }
                    /** reset the state **/
                    else{
                        pair=0;
                        left=0;
                        right=0;
                    }
                }
                result=max(result, pair);
            }
            return 2*result;
        }
    };

  • 1

    To solve this problem , the top voted answer just record all the invalid position, So we can calculate the range between all the invalid position pair-wise.

    Same Idea, and nice way to deal with my problem

    Code is like this

    class Solution {
    public:
        int longestValidParentheses(string s) {
            int n=s.size(), result=0;
            stack<int> s_stack;
            /** the valid index will be pop out **/
            /** the remained index is all in-valid **/
            for(int i=0; i<n; i++){
                if(s[i]=='(')  s_stack.push(i);
                else{
                    if(!s_stack.empty()){
                        if(s[s_stack.top()]=='(') s_stack.pop();
                        else  s_stack.push(i);
                    }
                    else
                        s_stack.push(i);
                }
            }
            if(s_stack.empty()) result=n;
            /** all the range based on the remained index in the stack is valid pairs **/
            /** scant the stack to get the result **/
            else{
                int end=n, start=0;
                while(!s_stack.empty()){
                    start=s_stack.top(); 
                    s_stack.pop();
                    result=max(result, end-start-1);
                    end=start;
                }
                result=max(result, end);
            }
            return result;
        }
    };

  • 4

    So can we use the dynamic programming to solve the problem.

    As with most cases, we use the tail-dynamic-programming method to solve this problem.

    we use

         dp[i]:  record the  max-pairs-end-at-position-i
    

    So, the recursive equation is like this

         if s[i]=='('      dp[i]=0
         if s[i]==')'      s[i-1]=='('     
                              dp[i]=dp[i-2]+2
                           s[i-1]==')'  &&  s[i-dp[i-1]-1]=='('     
                              dp[i]=d[i-1]+2+{dp[i-dp[i-1]-2] or 0}
    

    So the final implementation is like this:

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

  • 0
    2

    The mistake I made is like this

    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '(') {
            st.push(i);
        }
        else {
            if(!st.empty() && st.top() == '(')  st.pop();
            else  st.push(i);
        }
    }
    

  • 0
    2

    I should use s[st.top()] but not st.top()


Log in to reply
 

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