301.删除无效的括号
301.删除无效的括号
题解
题目：给定包含左右括号和字母的字符串，要求删除某些括号后，该字符串括号匹配（字母不删），如果只删1个就能合法，返回所有合法字符串，如果删2个才能合法…总之删除括号的数量越少越好
思路：
dfs+回溯
1.预处理出需要删除的左右括号的个数（rmL,rmR） 2.dfs遍历字符串，如果是左括号,则 temp := str[:i] + str[i+1:] dfs(temp, i, rml-1, rmR) 右括号同理 出口：rmL和rmR为0，并且字符串匹配
bfs
1.将字符串s存入队列 2.遍历队列，如果队列中的字符串合法则加入答案，遍历完后退出 3.如果没有合法的，则 遍历队列，遍历字符串 遇到括号就去除，加入队列 temp := str[:i] + str[i+1:]
代码
func removeInvalidParentheses(s string) (result []string) { mp := make(map[string]bool) rmL, rmR := 0, 0 for _, v := range s { if v == '(' { rmL++ } else if v == ')' { if rmL == 0 { rmR++ } else { rmL-- } } } var dfs func(str string, idx int, rmL, rmR int) dfs = func(str string, idx int, rml, rmR int) { if rml == 0 && rmR == 0 && isValid(str) { mp[str] = true return } if rml+rmR > len(str)-idx { return } for i := idx; i < len(str); i++ { v := str[i] if v == '(' && rml > 0 { temp := str[:i] + str[i+1:] dfs(temp, i, rml-1, rmR) } if v == ')' && rmR > 0 { temp := str[:i] + str[i+1:] dfs(temp, i, rml, rmR-1) } } } dfs(s, 0, rmL, rmR) for k := range mp { result = append(result, k) } return } func isValid(str string) bool { count := 0 for _, ch := range str { if ch == '(' { count++ } else if ch == ')' { count-- if count < 0 { return false } } } return count == 0 }
func removeInvalidParentheses(s string) (result []string) { cur := make(map[string]bool) cur[s] = true for { for str := range cur { if isValid(str) { result = append(result, str) } } if len(result) > 0 { return result } next := make(map[string]bool) for str := range cur { for i, v := range str { if v == '(' || v == ')' { temp := str[:i] + str[i+1:] next[temp] = true } } } cur = next } } func isValid(s string) bool { count := 0 for _, v := range s { if v == '(' { count++ } else if v == ')' { count-- if count < 0 { return false } } } return count == 0 }
type pair struct { count, cnt, idx int ss string } func removeInvalidParentheses(s string) (result []string) { ans := 0 n := len(s) mp := make(map[int][]string) mpSet := make(map[string]bool) vis := make(map[pair]bool) var dfs func(count, cnt, idx int, ss string) //count是左右括号匹配，cnt是还剩多少个字符 dfs = func(count, cnt, idx int, ss string) { p := pair{count, cnt, idx, ss} if !vis[p] { vis[p] = true } else { return } if count == 0 && idx == n { if cnt > ans { ans = cnt mpSet[ss] = true mp[ans] = append(mp[ans], ss) } else if cnt == ans { if !mpSet[ss] { mp[ans] = append(mp[ans], ss) mpSet[ss] = true } } } if count < 0 || cnt == -1 || idx == n { return } //去除当前 dfs(count, cnt-1, idx+1, ss) //不去除 if s[idx] == '(' { count++ } else if s[idx] == ')' { count-- } dfs(count, cnt, idx+1, ss+string(s[idx])) } dfs(0, n, 0, "") //左右是否匹配 还剩多少个字符 idx现在到哪了 字符串 for _, v := range mp[ans] { result = append(result, v) } return }
