LeetCode 32 Longest Valid Parentheses (C,C++,Java,Python)

Problem:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution:

维持一个字符栈和位置栈，字符栈记录没有匹配的字符，位置栈记录每一个入栈的字符的位置，如果入栈的是右括号，并且栈顶为左括号，则退栈，求出当前连续退栈的字符长度，求出这个最大值就是。

题目大意：

给一个字符串，只包含左括号和右括号，求出这个字符串合法括号的最大长度。

Java源代码（350ms）：

public class Solution {
    public int longestValidParentheses(String s) {
        int len=s.length(),max=0;
        Stack<Character> str_stack = new Stack<Character>();
        Stack<Integer> pos_stack = new Stack<Integer>();
        char[] str=s.toCharArray();
        for(int i=0;i<len;i++){
            if(str[i]=='('){
                str_stack.push('(');
                pos_stack.push(i);
            }else{
                if(str_stack.size()>0 && str_stack.peek().equals('(')){
                    str_stack.pop();
                    pos_stack.pop();
                    int tmp=pos_stack.size()==0?i+1:i-pos_stack.peek();
                    max=Math.max(max,tmp);
                }else{
                    str_stack.push(')');
                    pos_stack.push(i);
                }
            }
        }
        return max;
    }
}

C语言源代码（3ms）：

int longestValidParentheses(char* s) {
    int len=strlen(s),max=0,top=0,i,tmp;
    int* pos_stack=(int*)malloc(sizeof(int)*len);
    char* str_stack=(char*)malloc(sizeof(char)*len);
    for(i=0;s[i];i++){
        if(s[i]=='('){
            str_stack[top]='(';
            pos_stack[top]=i;
            top++;
        }else{
            if(str_stack[top-1]=='('){
                top--;
                if(top==0)tmp=i+1;
                else tmp=i-pos_stack[top-1];
                max=max>tmp?max:tmp;
            }else{
                str_stack[top]=')';
                pos_stack[top]=i;
                top++;
            }
        }
    }
    return max;
}

C++源代码（7ms）：

class Solution {
public:
    int longestValidParentheses(string s) {
        int max=0,top=0,len=s.size();
        int* pos_stack=(int*)malloc(sizeof(int)*len);
        char* str_stack=(char*)malloc(sizeof(char)*len);
        for(int i=0;i<len;i++){
            if(s[i]=='('){
                str_stack[top]='(';
                pos_stack[top]=i;
                top++;
            }else{
                if(str_stack[top-1]=='('){
                    int tmp;
                    top--;
                    if(top==0)tmp=i+1;
                    else tmp=i-pos_stack[top-1];
                    max=max>tmp?max:tmp;
                }else{
                    str_stack[top]=')';
                    pos_stack[top]=i;
                    top++;
                }
            }
        }
        return max;
    }
};

Python源代码（105ms）：

class Solution:
    # @param {string} s
    # @return {integer}
    def longestValidParentheses(self, s):
        length=len(s);top=0;Max=0
        str_stack=[' ' for i in range(length)]
        pos_stack=[0 for i in range(length)]
        for i in range(length):
            if s[i]=='(':
                str_stack[top]='('
                pos_stack[top]=i
                top+=1
            else:
                if top>0 and str_stack[top-1]=='(':
                    top-=1
                    tmp=i+1 if top==0 else i-pos_stack[top-1]
                    Max=Max if Max>tmp else tmp
                else:
                    str_stack[top]=')'
                    pos_stack[top]=i
                    top+=1
        return Max