在O(n)时间内查找字符串中最长有效括号序列的长度

Question

我的朋友在接受采访时遇到了一个问题,他被告知有一个O(n)解决方案.但是,我们都不能想到它.这是一个问题:

有一个字符串,它包含just,(并)找到最长有效括号子串的长度,它应该很好地形成.

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

我用动态编程想出来了,但它不是O(n).有任何想法吗？

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;
}

Answer 1

我以前做过这个问题,在压力下提出O(n)解决方案并不容易.这是它,用堆栈解决.

   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;
}