032_最长有效括号

Description

给定一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。

Example
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
Solution
func maxInt(a,b int)int  {
    if a > b  {
        return a
    }
    return b
}

//动态规划
func longestValidParentheses(s string) int {
    max := 0
    dp := make([]int,len(s))
    for i := 1;i <len(s); i ++ {
        if s[i] == ')'{
            if s[i-1] =='(' {
                if i >=2 {
                    dp[i] = dp[i-2]+2
                }else {
                    dp[i] = 2
                }
            }else if i - dp[i -1] > 0 && s[i - dp[i-1] -1]== '(' {
                if  i - dp[i-1] >= 2 {
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2]  +2
                }else {
                    dp[i] = dp[i-1] + 2
                }
            }
            max = maxInt(max,dp[i])
        }
    }
    return max
}

//Using stack 栈,
func longestValidParentheses2(s string) int {
    var stack []int
    max := 0
    stack = append(stack,-1)
    for i := 0; i < len(s);i ++ {
        if s[i]=='(' {
            stack = append(stack,i)
        }else {
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                stack = append(stack,i)
            }else {
                max = maxInt(max,i - stack[len(stack)-1])
            }
        }
    }
    return max
}
func longestValidParentheses1(s string) int {
    if len(s)<=1 {
        return 0
    }
    help := make([]bool,len(s))
    var stack  []int
    for i := 0;i < len(s);i ++{
        help[i] = false
    }
    for i := 0; i < len(s); i ++ {
        if s[i] == '('{
            stack = append(stack,i)
        }else {
            if len(stack) > 0{
                help[i] = true
                help[stack[len(stack)-1]] = true
                stack = stack[:len(stack)-1]
            }
        }
    }
    max,l := 0,0
    for i := 0; i < len(s);i ++ {
        if help[i] {
            l++
        }else {
            if max < l {
                max = l
            }
            l = 0
        }
    }
    return maxInt(max,l)
}

leetCode地址