Longest Valid Parentheses

Description

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

输出最长的左右括号匹配的子串长度

Solution

逐个字符扫描并记录左右括号长度，当左右括号数量相等时，左右括号达到全匹配。

如果只从左往右扫描，"((()"这种左括号多于右括号的会被判断为0，所以需要进行一次从右往左扫描。

"())()()"这种中间多出右括号的情况，需要重置计数器，从后面继续扫描。

func longestValidParentheses(s string) int {
    longest := 0

    left, right := 0, 0
    check_longest := func() {
        // 如果左右相等则此时左右括号匹配
        if left == right {
            if left * 2 > longest {
                longest = left * 2
            }
        }
    }

    // 从左往右扫描
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            left++
        } else {
            right++

            // 右括号多于左括号，则不满足连续匹配规则，需要重置
            if right > left {
                left, right = 0, 0
                continue
            }
        }

        check_longest()
    }

    left, right = 0, 0

    // 从右往左扫描
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '(' {
            left++

            // 左括号多于右括号，则不满足连续匹配规则
            if left > right {
                left, right = 0, 0
                continue
            }
        } else {
            right++
        }


        check_longest()
    }

    return longest
}

Similar Problem

20. Valid-Parentheses