LeetCode 上与“括号”有关的问题整理。
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true根据问题要求，有效的括号具备以下特征：
- 每个左括号都有一个右括号与之匹配，两者个数应该相等；
- 匹配的括号之间，不会有其他的半括号；
我们遍历字符串中的字符，使用一个栈来保存遇到的左括号；在遍历过程中，根据字符选择 入栈 或 出栈：
- 如果是左括号，就 push 到栈中；
- 如果是右括号：
- 如果栈为空，说明已遍历的子串中，右括号个数大于左括号，是无效子串，那么整体字符串也是无效的；
- 如果栈不为空，就 pop 出栈顶字符，判断与当前右括号是否能够组成有效的闭合括号；
遇到右括号时，pop 出栈顶字符这个操作，相当于“一个右括号抵消一个左括号”。当字符串遍历结束，如果栈不为空，说明左右括号个数不等，字符串是无效的。
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
// 是左括号就 push 进栈中
if (isLeft(ch)) {
stack.push(ch);
} else {
// 如果栈中没有前置字符，说明只有右括号没有左括号
if (stack.isEmpty()) {
return false;
}
// 判断与前置括号是否组成有效的闭合括号
if (!isClosed(stack.pop(), ch)) {
return false;
}
}
}
return stack.isEmpty();
}
private boolean isLeft(char ch) {
return ch == '(' || ch == '[' || ch == '{';
}
private boolean isClosed(char left, char right) {
return (left == '(' && right == ')')
|| (left == '[' && right == ']')
|| (left == '{' && right == '}');
}
}给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者 它可以被写作 (A)，其中 A 是有效字符串。 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())"
输出：1
这一题与《20. 有效的括号》 相似，判断左右括号是否相互匹配。
遍历一遍字符串，遇到一个右括号就抵消掉前面的一个左括号，最后把未抵消掉左括号和右括号个数相加。
class Solution {
public int minAddToMakeValid(String s) {
int left = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
if (left > 0) {
left--;
} else {
right++;
}
}
}
return left + right;
}
}数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
根据下面的定义，长的有效括号组合可以由较短的有效括号获得，如下图所示：
所以，n 对括号组成的有效括号组合可以由 n-1对括号组成的有效括号组合得到，依次类推，直到 n == 1。
n == 1，有效括号组合为：“()"；n == 2的有效括号组合，通过在n == 1的组合中元素的不同位置插入 “()” 得到，比如在前面插入、中间插入、后面插入，分别得到：“()()"、"(())"、"()()"；
使用这个方法，可以暴力求解出所有有效括号组合。
这是在给定的元素集合：左括号“(”、右括号")"，找到满足条件的所有组合，可以使用回溯求解“寻找组合”类的问题。
“回溯算法”的求解步骤如下：
1、选择列表
可供选择的元素只有“左括号、右括号”，所以选择列表是："(",")"。
2、路径
记录已经选择的左右括号，要求路径中的符号能够组成有效的括号对。
3、结束条件
- 当路径中“左括号”和“右括号”的个数都等于
n时，此时无法添加更多的符号，不需要再向下搜索。 - 从 20. 有效的括号 中我们知道，当路径中“右括号”个数大于“左括号”时，路径中的符号无法组成有效的括号对，不需要再继续搜索。
4、选择
什么条件下把“左括号”和“右括号”添加进路径中？
- 如果路径中“左括号”个数小于
n，把“左括号”添加进路径； - 如果路径中“右括号”个数小于“左括号”个数，且“右括号”个数小于
n，把“右括号”添加进路径；
5、空间状态树
定义函数 path 中已经有 left个“左括号” 和 right个“右括号”，继续搜索有效括号组合。
下图显示了 n=2 时构建的“空间状态树”：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
res.add("()");
for (int i = 2; i <= n; i++) {
Set<String> tmpSet = new HashSet<>();
List<String> tmpList = new LinkedList<>();
for (String param : res) {
for (int j = 0; j < param.length(); j++) {
String tmp = new StringBuilder(param).insert(j, "()").toString();
if (tmpSet.add(tmp)) {
tmpList.add(tmp);
}
}
}
res = tmpList;
}
return res;
}
}class Solution {
int n;
public List<String> generateParenthesis(int n) {
this.n = n;
List<String> res = new LinkedList<>();
backtrack(res, new StringBuilder(2 * n), 0, 0);
return res;
}
private void backtrack(List<String> res, StringBuilder path, int left, int right) {
if (left == n && right == n) {
res.add(path.toString());
return;
}
if (right > left) {
return;
}
if (left < n) {
path.append('(');
// 递归
backtrack(res, path, left + 1, right);
// 撤销选择
path.deleteCharAt(path.length() - 1);
}
if (right < left && right < n) {
path.append(')');
// 递归
backtrack(res, path, left, right + 1);
// 撤销选择
path.deleteCharAt(path.length() - 1);
}
}
}给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
要找到的是“格式正确且连续”的括号字符串最大长度，最直觉的做法是使用动态规划来求解，困难之处在于：怎么确定状态和转移方程。
动态规划中的”状态“是什么？有以下两种理解。
”状态“是：到字符串下标
基于这个状态，定义数组
状态转移方程：
- 如果
$s[i] = ')'$ ，且$s[i-1] = '('$ ，那么$dp[i] = dp[i-1] + 2$ ； - 如果
$s[i] = ')'$ ，但$s[i-1] = ')'$ ，需要找到与$s[i]$ 匹配的字符下标，因为$dp[i-1]$ 表示的是 “$s[0,...,i-1]$ 中最大的括号子串长度”，无法确定有效括号子串的下标范围，所以无法找到与$s[i]$ 匹配的字符下标，也就无法写出转移方程；
因此，这种“状态“是无效的。
“状态”是：以字符串下标
基于这个状态，定义数组
状态转移方程：
- 如果
$s[i] = ')'$ ，且$s[i-1] = '('$ ，那么$dp[i] = dp[i-1] + 2$ ； - 如果
$s[i] = ')'$ ，但$s[i-1] = ')'$ ，那么$s[i - dp[i-1],..., i-1]$ 是一个有效或无效的子串，$s[i]$ 匹配的字符位置下标为：$preIdx = i - 1 - dp[i-1] - 1$；如果$s[preIdx] = '('$ ，那么$dp[i] = dp[preIdx - 1] + dp[i - 1] + 2$ ；
因此，这种情况下的“状态”定义是有效的。
从上面的过程可以看出，关键是要找到与
public class Solution {
public int longestValidParentheses(String s) {
int res = 0, preIdx = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
if (i >= 2) {
dp[i] = dp[i - 2] + 2;
} else {
dp[i] = 2;
}
} else {
// preIdx : s[i] 对应的下标
preIdx = i - dp[i - 1] - 1;
// s[preIdx] 存在且是左括号
if (preIdx >= 0 && s.charAt(preIdx) == '(') {
// preIdx - 1 存在
if (preIdx - 1 >= 0) {
dp[i] = dp[preIdx - 1] + dp[i - 1] + 2;
} else {
dp[i] = dp[i - 1] + 2;
}
}
}
res = Math.max(res, dp[i]);
}
}
return res;
}
}给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
最直接的思路是：依次删除1个字符、2个字符、... 判断删除后的字符串是否是有效括号字符串。
这相当于，每次从字符串中删除1个字符、2个字符、...，剩余有效括号的组合有多少个，变成了一个求解组合的问题。这种问题可以使用回溯算法求解。
代码实现如下所示，为了在回溯过程中能够实现剪枝，使用参数 MAX_LEN 记录当前有效字符串的最大长度，如果要检测的字符串长度小于 MAX_LEN，就没有必要再检测了。
这个方法的时间复杂度很高，最差情况是：$O(N^{N+1})$，无法通过 LeetCode 上的第71个测试用例。
在方法1中，我们是枚举了删除字符的所有情况，实际上我们不需要遍历所有情况。
问题要求“删除最少的括号”，我们首先要计算出，要删除多少个左括号和右括号，只要剩余要删除的左括号和右括号个数为0，就表示当前字符串可能是有效的。
求解的思路如下：
1、遍历字符串，计算出要删除的左括号个数 l2remove、右括号个数 r2remove；
2、遍历字符串，尝试删除当前字符 char：
- 如果 l2remove > 0，且 char == '('，就删除当前字符；
- 如果 r2remove> 0，且 char == ')'，就删除当前字符；
3、记录当前已经使用的左括号个数 lCount、右括号个数 rCount，如果 rCount > 0，那么后面再怎么组合，都不可能变成有效括号。
在回溯过程中，可以利用一下剪枝方法来提升效率：
- 如果 l2remove + r2remove 的值大于字符串剩余要遍历的个数，说明剩下的字符串一定是无效的，就停止搜索；
- 在每次进行搜索时，如果遇到连续相同的括号我们只需要搜索一次即可，比如当前遇到的字符串为 "(((())"，去掉前四个左括号中的任意一个，生成的字符串均为 "((())"；
我们可以假设有一棵树来保存每一个子串，如下图所示：
我们要做的就是层序遍历这棵树，把合法的节点保存进结果集。在遍历下一层前，如果结果集中已经有数据了，就结束遍历。
这个思路与”官方题解-方法二：广度优先搜索“相同。
class Solution {
int MAX_LEN = 0;
public List<String> removeInvalidParentheses(String s) {
Map<Integer, Set<String>> map = new HashMap<>(s.length());
int left = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
left++;
}
if (ch == ')') {
right++;
}
}
backtrack(map, s, left, right);
for (int i = s.length(); i >= 0; i--) {
if (map.containsKey(i)) {
return new ArrayList<>(map.get(i));
}
}
return new ArrayList<>();
}
private void backtrack(Map<Integer, Set<String>> map, String str, int left, int right) {
int len = str.length();
// 只有当前字符串长度 >= MAX_LEN 才有必要保存
if (len < MAX_LEN) {
return;
}
// 只有左右括号个数相等时，才有可能是有效的括号字符串
if (left == right) {
if (isValid(str)) {
if (!map.containsKey(len)) {
map.put(len, new HashSet<>());
}
map.get(len).add(str);
MAX_LEN = len;
return;
}
}
// 遍历结束了
if (len == 0) {
map.put(0,
new HashSet<String>() {{
add("");
}}
);
return;
}
// 依次移除每一个位置的字符，然后回溯
for (int i = 0; i < len; i++) {
char ch = str.charAt(i);
// 跳过字母
if(Character.isLetter(ch)) {
continue;
}
if (ch == '(') {
left--;
}
if (ch == ')') {
right--;
}
String newStr = new StringBuilder(str).deleteCharAt(i).toString();
backtrack(map, newStr, left, right);
if (ch == '(') {
left++;
}
if (ch == ')') {
right++;
}
}
}
private boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}class Solution {
private List<String> res = new LinkedList<>();
public List<String> removeInvalidParentheses(String s) {
int l2remove = 0, r2remove = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
l2remove++;
} else if (ch == ')') {
if (l2remove == 0) {
r2remove++;
} else {
l2remove--;
}
}
}
// 回溯求解
helper(s, 0, 0, 0, l2remove, r2remove);
return res;
}
private void helper(String str, int start, int lCount, int rCount, int l2remove, int r2remove) {
// 当 l2remove 和 r2remove 都是 0 时，表示此时字符串中左右括号数相等，判断有效性
if (l2remove == 0 && r2remove == 0) {
if (isValid(str)) {
res.add(str);
}
return;
}
// 依次移除当前字符
for (int i = start; i < str.length(); i++) {
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if (l2remove + r2remove > str.length() - i) {
return;
}
// 如果遇到连续相同的括号我们只需要搜索一次即可，比如当前遇到的字符串为 "(((())"，去掉前四个左括号中的任意一个，生成的字符串是一样的，均为 "((())"，
if (i != start && str.charAt(i) == str.charAt(i - 1)) {
if (str.charAt(i) == '(') {
lCount++;
} else if (str.charAt(i) == ')') {
rCount++;
}
continue;
}
// 尝试去掉当前的左括号
if (l2remove > 0 && str.charAt(i) == '(') {
helper(str.substring(0, i) + str.substring(i + 1), i, lCount, rCount, l2remove - 1, r2remove);
}
// 尝试去掉当前的右括号
if (r2remove > 0 && str.charAt(i) == ')') {
helper(str.substring(0, i) + str.substring(i + 1), i, lCount, rCount, l2remove, r2remove - 1);
}
// 前面没有去掉当前字符，判断已经使用的左右括号的个数是否相等
// 如果已经使用的右括号数大于左括号树，后面再怎么添加，都不可能组成有效的括号
if (str.charAt(i) == '(') {
lCount++;
} else if (str.charAt(i) == ')') {
rCount++;
}
if (rCount > lCount) {
break;
}
}
}
private boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}class Solution {
public List<String> removeInvalidParentheses(String s) {
LinkedHashSet<String> list = new LinkedHashSet<>();
list.add(s);
List<String> ans = new LinkedList<>();
while (!list.isEmpty()) {
for (String str : list) {
if (isValid(str)) {
ans.add(str);
}
}
if (!ans.isEmpty()) {
return ans;
}
// 遍历每个字符串，把它的所有子串（子节点）添加进列表中
LinkedHashSet<String> tmpList = new LinkedHashSet<>();
for (String str : list) {
for (int i = 0; i < str.length(); i++) {
if (i > 0 && str.charAt(i) == str.charAt(i - 1)
|| Character.isLetter(str.charAt(i))) {
continue;
}
// 删除括号，添加进临时集合中
if (str.charAt(i) == '(' || str.charAt(i) == ')') {
tmpList.add(str.substring(0, i) + str.substring(i + 1));
}
}
}
list = tmpList;
}
return ans;
}
private boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}public boolean checkValidString(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
// BC1：对角线上元素是否有效
for (int i = 0; i < n; i++) {
dp[i][i] = s.charAt(i) == '*';
}
// BC2：对角线上 [i,i+1] 是否是有效括号
for (int i = 1; i < n; i++) {
char c1 = s.charAt(i - 1), c2 = s.charAt(i);
dp[i - 1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
}
// 开始遍历其他位置的元素
for (int i = n - 3; i >= 0; i--) {
char c1 = s.charAt(i);
for (int j = i + 2; j < n; j++) {
char c2 = s.charAt(j);
// 1、如果 s[i]、s[j] 能单独组成有效括号，那么 dp[i][j] 是否是有效括号，由 dp[i + 1][j - 1] 决定
if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
dp[i][j] = dp[i + 1][j - 1];
}
// 2、如果 dp[i+1][j-1] 不是有效的，但是存在 s[k]，令 dp[i][k]、dp[k+1][j] 是有效的，那么 dp[i][j] 也是有效的
for (int k = i; k < j && !dp[i][j]; k++) {
dp[i][j] = dp[i][k] && dp[k + 1][j];
}
}
}
return dp[0][n - 1];
}在遍历的过程中，要给遇到的每个右括号找到一个前置的左括号或星号，相互抵消。如果右括号的个数大于左括号（左括号抵消后个数为0），那么一定是无效字符串。
当遍历完字符串后，判断剩余的左括号个数是否小于星号，且左括号的下标要小于星号。
遍历剩余的星号和左括号，每个星号抵消一个左括号；当星号没有剩余后，如果左括号还有剩余，就说明有多余的左括号。
class Solution {
public boolean checkValidString(String s) {
Stack<Integer> left = new Stack<>();
Stack<Integer> star = new Stack<>();
int n = s.length();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == '(') {
left.push(i);
} else if (ch == '*') {
star.push(i);
} else {
if (!left.isEmpty()) {
left.pop();
} else if (!star.isEmpty()) {
star.pop();
} else {
return false;
}
}
}
// 判断 left 和 star 是否为空
while (!left.isEmpty() && !star.isEmpty()) {
if (left.peek() > star.peek()) {
return false;
} else {
left.pop();
star.pop();
}
}
return left.isEmpty();
}
}class Solution {
public boolean checkValidString(String s) {
int lmin = 0, lmax = 0;
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (ch == '(') {
lmin++;
lmax++;
} else if (ch == ')') {
lmin--;
lmax--;
if (lmax < 0) {
return false;
}
} else {
lmin--;
lmax++;
}
lmin = Math.max(lmin, 0);
}
return lmin == 0;
}
}给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
- () 得 1 分。
- AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
- (A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出： 1