查找字符串中最长的有效括号序列的长度，以O(n)时间为单位 [英] Find the length of the longest valid parenthesis sequence in a string, in O(n) time

问题描述

我的朋友在一次采访中遇到一个问题，他被告知有O(n)解决方案.但是，我们两个都没有想过.这是问题:

My friend ran into a question in an interview and he was told that there is an O(n) solution. However, neither of us can think it up. Here is the question:

有一个仅包含(和)的字符串，查找最长有效括号子字符串的长度，该字符串应格式正确.

There is a string which contains just ( and ), find the length of the longest valid parentheses substring, which should be well formed.

例如)()())" ，最长的有效括号是()()，长度为4.

For example ")()())", the longest valid parentheses is ()() and the length is 4.

我通过动态编程解决了这个问题，但不是O(n).有什么想法吗?

I figured it out with dynamic programming, but it is not O(n). Any ideas?

public int getLongestLen(String s) {
    if (s == null || s.length() == 0)
        return 0;

    int len = s.length(), maxLen = 0;
    boolean[][] isValid = new boolean[len][len];
    for (int l = 2; l < len; l *= 2)
        for (int start = 0; start <= len - l; start++) {
            if ((s.charAt(start) == '(' && s.charAt(start + l - 1) == ')') && 
                (l == 2 || isValid[start+1][start+l-2])) {
                    isValid[start][start+l-1] = true;
                    maxLen = Math.max(maxLen, l);
                }
        }

    return maxLen;
}

推荐答案

我之前曾做过这个问题，在压力下提出O(n)解决方案并不容易.就是这个，这是通过堆栈解决的.

I did this question before, and it is not easy to come up with O(n) solution under pressure. Here is it, which is solved with stack.

   private int getLongestLenByStack(String s) {
    //use last to store the last matched index
    int len = s.length(), maxLen = 0, last = -1;
    if (len == 0 || len == 1)
        return 0;

    //use this stack to store the index of '('
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < len; i++) {
        if (s.charAt(i) == '(') 
            stack.push(i);
        else {
            //if stack is empty, it means that we already found a complete valid combo
            //update the last index.
            if (stack.isEmpty()) {
                last = i;        
            } else {
                stack.pop();
                //found a complete valid combo and calculate max length
                if (stack.isEmpty()) 
                    maxLen = Math.max(maxLen, i - last);
                else
                //calculate current max length
                    maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }

    return maxLen;
}

这篇关于查找字符串中最长的有效括号序列的长度，以O(n)时间为单位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！