小编Bra*_*ram的帖子

我的朋友在接受采访时遇到了一个问题,他被告知有一个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])) …