LeetCode 32 Longest Valid Parentheses

题目大意是给定一个只有左右括号组成的字符串,求最长的valid字串长度,比如“()”的最长valid字串长度为2,“)()())”的最长valid字串为”()()“,则长度为4.

拿到这个题目第一反应就是用Stack,但是Stack里面装什么呢?如何表示Valid最大长度?后来想到是否能够把还没匹配好的括号的index放到stack中,如果有匹配的就pop,没有就push。当pop的时候判断stack是否为空,如果空了,则该index之前的字串都是valid;如果不为空,则该index与stack中的peek之差就是当前valid子串的长度。 代码如下:

public class Solution {  
    public int longestValidParentheses(String s) {  
        int max = 0;  
        if (s == null || s.isEmpty()) return max;  
        int len = s.length();  
        Stack<Integer> stack = new Stack<Integer>();  
        for (int i=0; i<len; i++) {  
            char c = s.charAt(i);  
            if (c == ')' && !stack.isEmpty() && s.charAt(stack.peek()) == '(') {  
                stack.pop();  
                if (stack.isEmpty()) {  
                    max  = i+1;  
                } else {  
                    int valid_len = i - stack.peek();  
                    max = max > valid_len ? max : valid_len;  
                }  
            } else {  
                stack.push(i);  
            }  
        }  
        return max;  
    }  
}  

看到一篇博文,也可以用一维DP去解,等有空时再细研究。附上链接:点击打开链接

作者:ywheel
本文出处:http://blog.ywheel.cn/post/2015/03/08/leetcode_32/
文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。