Longest Valid Parentheses

题目描述

最长有效括号

给定一个只包含(和)的字符串，返回最长有效括号子串的长度。

示例：

输入：s = "(()"
输出：2

解法

解法一：动态规划

用dp[i]表示以位置i结尾的字符拥有的最长子串。

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func longestValidParentheses(s string) int {
    max := 0
    n := len(s)
    dp := make([]int, n)
    for i := 1; i < n; i++ {
        ch := s[i]
        if ch == '(' {
            continue
        }

        start := i - 1 - dp[i-1]
        if start >= 0 && s[start] == '(' {
            if start > 0 {
                dp[i] = dp[i-1] + dp[start-1] + 2
            } else {
                dp[i] = dp[i-1] + 2
            }
        }

        if max < dp[i] {
            max = dp[i]
        }
    }
    return max
}

解法二：栈

• 时间复杂度：O(n)

• 空间复杂度：O(n)

func longestValidParentheses(s string) int {
    ans := 0
    stack := []int{}
    stack = append(stack, -1)
    for i := range s {
        if s[i] == '(' {
            stack = append(stack, i)
            continue
        }
        stack = stack[:len(stack)-1]
        if len(stack) == 0 {
            stack = append(stack, i)
        } else {
            last := stack[len(stack)-1]
            if ans < i-last {
                ans = i - last
            }
        }
    }
    return ans
}

解法三：两次遍历

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func longestValidParentheses(s string) int {
    left, right := 0, 0
    ans := 0
    for i := 0; i < len(s); i++ {
        if s[i] == ')' {
            right++
        } else {
            left++
        }
        if right == left {
            if ans < left+right {
                ans = left + right
            }
        }
        if right > left {
            right, left = 0, 0
        }
    }
    left, right = 0, 0
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == ')' {
            right++
        } else {
            left++
        }
        if right == left {
            if ans < left+right {
                ans = left + right
            }
        }
        if right < left {
            right, left = 0, 0
        }
    }
    return ans
}