leetcode-go/hard/32.go

package main

import (
	"fmt"
)

// 穷举
func longestValidParenthesesOld(s string) int {
	pair := 0
	for i := 0; i < len(s); i++ {
		left, right := 0, 0
		for j := i; j < len(s); j++ {
			if s[j] == '(' {
				left++
			} else {
				right++
			}
			if right > left {
				break
			}
			if left == right && left > pair {
				pair = left
			}
		}
	}
	return pair * 2
}

func maxInt(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func longestValidParentheses(s string) int {
	stack := []int{}
	// max: longest length, beg: idx of last ')' before current stack
	max, beg := 0, -1
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, i)
		} else if s[i] == ')' {
			if len(stack) > 0 {
				// pop last '('
				stack = stack[:len(stack)-1]
			} else {
				beg = i
				continue
			}
			if len(stack) == 0 {
				// curr idx is the end of curr seq
				max = maxInt(max, i-beg)
			} else {
				// top of stack is the beg of curr seq
				max = maxInt(max, i-stack[len(stack)-1])
			}
		}
	}
	return max
}

func main() {
	fmt.Println(longestValidParentheses("("))
	fmt.Println(longestValidParentheses("()()("))
	fmt.Println(longestValidParentheses("()(((()(()(((()(()())))(()"))
}