Longest Valid Parentheses, Leetcode 解题笔记

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.

遇到此题第一反应就是Stack,遇到左括号push,遇到右括号pop。一开始我向stack里存的是括号本身,然后用一个counter来记录长度。结果发现一些特殊的case不能通过,参考别人算法后发现stack里应该存的是括号在string s中的index。具体算法如下:

(1) 如果当前栈为空,则说明加上当前右括号没有合法序列(有也是之前判断过的);
(2) 否则弹出栈顶元素,如果弹出后栈为空,则说明当前括号匹配,我们会维护一个合法开始的起点start,合法序列的长度即为当前元素的位置-start+1;否则如果栈内仍有元素,则当前合法序列的长度为当前栈顶元素的位置下一位到当前元素的距离,因为栈顶元素后面的括号对肯定是合法的,而且左括号出过栈了。
因为只需要一遍扫描,算法的时间复杂度是O(n),空间复杂度是栈的空间,最坏情况是都是左括号,所以是O(n)

public class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> store = new Stack<Integer>();
        int i = 0;
        int start = 0;
        if(s == null || s.length() == 0) return 0;
        
        while(i < s.length()){
            if(s.charAt(i) == '('){
                store.push(i);
            }
            else{
                if(store.empty()){
                    start = i+1;
                }
                else{
                    store.pop();
                    if(store.empty()){
                        max = Math.max(max, i-start+1);
                    }
                    else{
                        max = Math.max(max, i-store.peek());
                    }
                }
            }
            i++;
        }
        return max;
    }
}

一个让我迷惑的地方是”(())”这个string的答案到底是2还是4,后来发现根据题目的本意,此处答案应为4。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s