leetcode: 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.

原问题链接：https://leetcode.com/problems/longest-valid-parentheses/

 

问题分析

    在求最长合法的括号串之前，我们先来看一下如果给定一个字符串，如果要判断它是否为合法的括号串该怎么做。 在之前的一些文章里也讨论过，要处理这样的问题，可以用一个栈。遍历字符串中间每个元素的时候每次碰到左括号的时候就将它入栈，碰到右括号的时候就来查看栈的情况。如果栈非空而且栈顶的元素是左括号则表示当前找到一对匹配的括号。我们会将当前栈顶的元素弹出来。否则表示当前的串不是一个合法的符号串。在遍历结束后如果栈是空的，表示这整个串是合法的括号串，否则表示非法的串。

　　上述描述的判断一个串是否为合法括号串的方法有一个特点，如果它整体是合法的，则参与运算的栈最终是空的。在目前的问题里，给定的一个串可能里面部分串是一个合法的括号串，也可能它整个本身就是一个合法的括号串。那么我们针对这些情况来讨论一下。

　　很明显，当按照前面的过程，如果最后整个栈是空的，也就是说整个串就是合法的串，那么很简单，我们直接返回这个串的长度就可以了。那么对于它部分是合法串的情况呢？在遍历的过程中必然会有一些元素存在于栈中。这些在栈中的元素相当于一个个的分隔点，在这些点之间如果存在有空隙的话，这些空隙其实就相当于一些合法串。所以我们最终就是要在遍历完之后找到这些长度最大的空隙，也就找到了最长的括号串。有了上述的思路，在实现的时候还可以稍微做一些修改。

　　我们在每次碰到当前字符为')'而且栈顶元素为'('的时候，表示当前找到了一个匹配。这个时候我们要求的最长的段应该是从当前的索引i到栈里头除了栈顶这个元素之后的那个元素之间距离。因为按照前面的推理，还留在栈里的元素就是针对当前长度来说没有找到匹配的。所以只要计算一下当前元素和这个元素后面那个元素之间的距离就可以了。当然，还有一些边界条件，比如说除了匹配的'('之后当前的栈已经空了，这说明我们匹配到串的最开始。为了统一各种条件，我们可以在最开始向栈里加入一个元素-1。以后碰到的元素只要和匹配的'('下面的那个元素相减就可以了。具体的实现见如下的代码：

 

public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
                stack.pop();
                result = Math.max(result, i - stack.peek());
            } else {
                stack.push(i);
            }
        }
        return result;
    }
}

 

 

另一种解法

    其实这个问题还有另外一种解决思路。就是我们从左到右遍历整个字符串的时候，一个合格的括号串它是在任何一个位置保证左括号的数量大于等于右括号的数量的。所以我们可以用一个数字来记录当前左括号的数量。当碰到一个左括号的时候这个数字就加一，碰到右括号的时候如果本身左括号的数量大于零，就表示找到了一个匹配，将左括号数减一。

    当然，如果只是这样子还是不能得到最长合法括号串。我们需要定义一个和字符串等长的整型数组，用来记录当前某个位置所匹配的长度。比如说我们有串"()"，在索引０的位置匹配的长度为０，而在索引１的位置，它匹配的长度为２。

　　对于数组中任意的一个位置i来说，当碰到一个匹配的时候dp[i] = dp[i - 1] + 2。当然，这里是否就概括了所有的情况呢？针对"(())"这种类型的来说，我们一个右括号碰到的和它匹配的左括号不是在它连着的左边，或者在数组的开头有"()"。针对这种情况dp[i] = dp[i - 1] + 2确实是成立的。但是还有一些情况就是它们匹配的情况之前还有一部分。比如说"()()"，针对索引３的位置来说，它得到的值是２。但是在它之前还有一个匹配的部分，这里真实的最长的合法串应该还要加上前面那个位置的匹配。所以应该是dp[i] += dp[i - dp[i]]。当然，在具体的实现中要保证i - dp[i] >= 0。所以按照这种方式得以得到如下的一个实现：

 

public class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int result = 0;
        int leftCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                leftCount++;
            } else if (leftCount > 0){
                dp[i] = dp[i - 1] + 2;
                dp[i] += (i - dp[i]) >= 0 ? dp[i - dp[i]] : 0;
                result = Math.max(result, dp[i]);
                leftCount--;
            }
        }
        return result;
    }
}

　　这种实现不需要使用栈来保存匹配的位置信息，减少了一些入栈和出栈的操作，所以整体的执行效率更加高。整体的时间复杂度在O(N)的范围。

 

总结

　　判断合法括号串的方法有一个固定的套路。但是在结合具体问题来讨论，比如在一个串里找最大合法括号串的时候，我们可以利用合法串里左括号和右括号数量相等而且任何位置都是左括号数量大于等于右括号数量的条件。在第二种方法里，我们通过一个判断dp[i]和dp[i - dp[i]]的位置关系可以将一些连续的合法串的长度计算出来，避免了还需要后面回头去遍历计算。

 

参考材料

https://leetcode.com/discuss/83428/java-solutions-with-explanation-stack-short-easy-understand