LeetCode题目:Longest Valid Parentheses

By | 2012 年 9 月 30 日

关键问题在于括号对能匹配的条件是左右括号数目相等。
然后已经匹配的长度有可能扩散到下一次匹配,比如()(),在第二次右括号匹配的时候,当时的长度要计算上被匹配的左括号左边的成功匹配长度。



Longest Valid Parentheses
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.

code rewrite 2018-04-08 C++

// for speeding up the execution
static const auto io_speed_up = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int longestValidParentheses(string s) {        
        int max_len = 0;

        int * stack = new int[s.length() + 1];
        int si = 0;
        stack[0] = -1;

        for(int i = 0; i < s.length(); i++) {
            if( '(' == s[i] ) {
                stack[++si] = i;
            } else {
                if( si > 0 ) {
                    --si;
                    int len = i - stack[si];
                    if( len > max_len ) max_len = len;
                } else {
                    stack[0] = i;
                }
            }
        }

        return max_len;
    }
};

code rewrite 2018-04-08 C++

class Solution {
public:
    int longestValidParentheses(string s) {
        int potential_left = -1; // the hard left boundery of potential valid substring
        int max_len = 0;

        std::stack<int> stack;
        for(int i = 0; i < s.length(); i++) {
            if( '(' == s[i] ) {
                stack.push(i);
            } else {
                if( stack.size() > 0 ) {
                    stack.pop();
                    // if stack is not empty, then the top index in stack is the unpaired open parentheis after solve the ) at index i
                    // otherwise, the whole string (potential_left, i] is valid substring
                    int left = stack.size() == 0 ? potential_left : stack.top();
                    int len = i - left;
                    if( len > max_len )
                        max_len = len;
                } else {
                    potential_left = i; //substring from this position can not be valid.
                }
            }
        }

        return max_len;
    }
};

code rewrite 2018-04-07 C++

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = 0; //tracking current length of valid substring
        int prev_len = 0; //length of valid substring that possible to connect to the adjancent open parentheses
        int max_len = 0;

        std::stack<int> stack;
        for(int i = 0; i < s.length(); i++) {
            if( '(' == s[i] ) {
                stack.push(prev_len);
                stack.push(i);
                prev_len = 0;
            } else {
                if( stack.size() > 0 ) {
                    int open_index = stack.top(); stack.pop();
                    int prev_len_connected = stack.top(); stack.pop();
                    len = i - open_index + 1 + prev_len_connected;
                    max_len = max_len >= len ? max_len : len;
                    prev_len = len;
                } else {
                    prev_len = 0;
                }
            }
        }

        return max_len;
    }
};



代码:O(n)

struct Info{
    int index;
    int bonus;
};
class Solution {
public:
    int longestValidParentheses(string s) {
        vector ls;//left parentheses that not matched
        int maxlen = 0;
        int curBonus = 0;
        for(int i = 0 ; i < s.size(); ++i) {
            if(s[i] == '(') {
                Info info;info.index = i;info.bonus = curBonus;
                curBonus = 0;
                ls.push_back(info);
            } else {
                curBonus = 0;
                if(ls.size() > 0) {
                    Info lastleft = ls[ls.size() - 1];
                    ls.pop_back();
                    int len = i - lastleft.index + 1 + lastleft.bonus;
                    curBonus = len;
                    if(maxlen < len)
                        maxlen = len;
                }
            }
        }
        return maxlen;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注