删除无效的括号

1. 题目描述

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

2. 思路

1. 思路一
   • 全排列
   • 遍历每个字符，对于这个字符，可以加入path，也可以不加入
   • 找出所有的路径后验证是否合法括号，取出最长的那个

3. 实现

3.1. 全排列

var m = map[rune]rune{
	'(': ')',
}

func removeInvalidParentheses(s string) []string {
	path := make([]rune, 0)
	set := make(map[string]bool, 0)
	removeInvalidParenthesesDFS([]rune(s), 0, &path, set)

	maxCount := 0
	for str := range set {
		maxCount = max(maxCount, len(str))
	}

	res := make([]string, 0)
	for str := range set {
		if len(str) == maxCount {
			res = append(res, str)
		}
	}
	return res
}

func removeInvalidParenthesesDFS(runes []rune, index int, path *[]rune, set map[string]bool) {
	if isValid(*path) {
		set[string(*path)] = true
	}

	if index == len(runes) {
		return
	}

	//加上index位置的字符
	*path = append(*path, runes[index])
	removeInvalidParenthesesDFS(runes, index+1, path, set)
	*path = (*path)[:len(*path)-1]
	//不加index位置的字符
	removeInvalidParenthesesDFS(runes, index+1, path, set)

}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func isValid(s []rune,) bool {
	stack := make([]rune, 0)
	for _, r := range s {
		if isLeft(r) {
			stack = append(stack, r)
		} else if isRight(r) {
			if len(stack) > 0 && isMatch(stack[len(stack)-1], r) {
				stack = stack[:len(stack)-1]
				continue
			}
			return false
		}
	}

	return len(stack) == 0
}

func isLeft(r rune) bool {
	return r == '('
}

func isRight(r rune) bool {
	return r == ')'
}

func isMatch(left, right rune) bool {
	return m[left] == right
}

4. 参考

• 【一分钟内看懂】将括号的「是否合法」转化为「数学判定」 - 删除无效的括号 - 力扣（LeetCode）