Leetcode-32:Longest Valid Parentheses

2018-01-17

问题描述：

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

问题示例

1
2
3

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.

我的答案

//从前往后，每遇到一个符号就放入vector,若遇到")"，则在当前vector从后往前找，找到第一个"(",替换"("为"0"，一个"0"代表一组"()"
int longestValidParentheses(string s) {
    vector<char> temp;
    vector<char>::iterator iter;
    int max = 0;
    int currentmax = 0;
    int j;
    if(s.length() == 0){
        return 0;
    }
    for (int i=0; i<s.length(); i++) {
        if(s[i] == ')'){
            for (j = temp.size()-1; j>=0; j--) {
                if(temp[j] == ')'){
                    temp.push_back(')');
                    break;
                }else if(temp[j] == '('){
                    temp[j] = '0';
                    break;
                }
            }
            if(j == -1){
                temp.push_back(')');
            }
        }else{
            temp.push_back('(');
        }
    }
    for (j = 0; j<temp.size(); j++) {
        printf("%c",temp[j]);
        if(temp[j] == '0'){
            currentmax+=2;
        }else{
            if(currentmax>max){
                max = currentmax;
            }
            currentmax = 0;
        }
    }
    if(currentmax>max){
        max = currentmax;
    }
    return max;
}

其他高效答案

int longestValidParentheses(string s) {
        if(s.empty() | s.length() <= 1) return 0;
        int rw = 0, n = s.length();
        
        int last[2 * n + 2];
        int longest = 0;
        for(int i = 0; i < 2 * n + 2; i++) last[i] = -2;
        
        last[n] = -1;
        for(int i = 0; i < s.length(); i++){
            if(s[i] == ')') {
                last[rw + n] = -2;
                rw--;
                if(last[rw + n] != -2) {
                    longest = max(longest, i - last[rw + n] );
                    //cout<<last[rw + n]<<" "<<i<<" "<<rw<<endl;
                } else {
                    last[rw + n] = i;
                }
            } else {
                rw++;
                if(last[rw + n] == -2) {
                    last[rw + n] = i;
                }
            }
        }
        return longest;
    }