[数据结构与算法]LeetCode 301打卡记录2021.10.27

LeetCode 301 删除无效的括号

题目描述

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

返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = “()())()”
输出：["(())()","()()()"]

示例 2：
输入：s = “(a)())()”
输出：["(a())()","(a)()()"]

示例 3：
输入：s = “)(”
输出：[""]

解题思路

知识点：DFS、剪枝

将字符串遍历，判断左括号“（”与右括号“）”匹配，得到左括号的溢出值visitedLeft（可以为负数，意味着“）”的数量大于“（” ）。

递归使用DFS，依次获得符合标准的字符串

注意点：
1.判断下标是否到了字符串末尾
2.判断多个右括号是否删除时，前面需有相应匹配数量的左括号
3.使用map插入符合条件的字符串，进行去重