0301.remove-invalid-parentheses.go

package _0301

func isValid(str string) bool {
	cnt := 0
	for _, ch := range str {
		if ch == '(' {
			cnt++
		} else if ch == ')' {
			cnt--
			if cnt < 0 {
				return false
			}
		}
	}
	return cnt == 0
}

func helper(ans *[]string, str string, start, lremove, rremove int) {
	if lremove == 0 && rremove == 0 {
		if isValid(str) {
			*ans = append(*ans, str)
		}
		return
	}

	for i := start; i < len(str); i++ {
		if i != start && str[i] == str[i-1] {
			continue
		}

		if lremove+rremove > len(str)-i {
			return
		}

		if lremove > 0 && str[i] == '(' {
			helper(ans, str[:i]+str[i+1:], i, lremove-1, rremove)
		}

		if rremove > 0 && str[i] == ')' {
			helper(ans, str[:i]+str[i+1:], i, lremove, rremove-1)
		}
	}
}

func removeInvalidParentheses(s string) []string {
	l, r := 0, 0
	var ans []string
	for _, ch := range s {
		if ch == '(' {
			l++
		} else if ch == ')' {
			if l == 0 {
				r++
			} else {
				l--
			}
		}
	}

	helper(&ans, s, 0, l, r)
	return ans
}