1.有效的括号（20-易）
题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例：
输入：s = "()[]{}"
输出：true
思路：本题核心还是栈的应用：
- 直接栈：遇到左括号，压栈右括号，其他都要出栈比较
- 映射+栈：代码是压左括号，遇到右括号出栈（映射的key），比较映射值与栈顶值是否相同。
两种思路的共同点是遇到右括号一定出栈比较！
代码：
class Solution {
// 直接使用栈
public boolean isValid(String s) {
if (s.length() % 2 == 1) {
return false;
}
Deque<Character> stack = new LinkedList<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{'){
stack.push('}');
} else if (stack.isEmpty() || c != stack.pop()) {
return false;
}
}
return stack.isEmpty();
}
// 栈 + 映射(本质一样)
private static final Map<Character,Character> map = new HashMap<>(){{
put(')', '(');
put(']', '[');
put('}', '{');
}};
public boolean isValid(String s) {
if (s.length() % 2 == 1) {
return false;
}
Deque<Character> stack = new LinkedList<>();
for(Character c : s.toCharArray()){
if (map.containsKey(c)) {
if (stack.isEmpty() || map.get(c) != stack.pop()) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
2.括号生成（22-中）
题目描述：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
思路：本题可以使用深度优先遍历（推荐），可以记录当前递归得到的结果，所以不用进行回溯：
- 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支，即右边使用的括号大于左边使用的括号就剪枝；
- 终止条件：左右括号都用完
ps：可以使用括号累加或者减少，代码如下。
代码：
// 做加法统计
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
if (n == 0) return ans;
dfs("", 0, 0, n, ans);
return ans;
}
public void dfs(String curStr, int left, int right, int n, List<String> ans) {
if (left == n && right == n) {
ans.add(curStr);
return;
}
if (left < right) { // 剪枝
return;
}
if (left < n) {
dfs(curStr + "(", left + 1, right, n, ans);
}
if (right < n) {
dfs(curStr + ")", left, right + 1, n, ans);
}
}
// 做减法统计
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
if (n == 0) return ans;
dfs("", n, n, ans);
return ans;
}
public void dfs(String curStr, int left, int right, List<String> ans) {
if (left == 0 && right == 0) {
ans.add(curStr);
return;
}
if (left > right) { // 剪枝
return;
}
if (left > 0) {
dfs(curStr + "(", left - 1, right, ans);
}
if (right > 0) {
dfs(curStr + ")", left, right - 1, ans);
}
}
3.括号匹配深度（补充）
题目描述："","()","()()","((()))"都是合法的括号序列 对于一个合法的括号序列我们又有以下定义它的深度:
空串""的深度是0
如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y)
如果"X"的深度是x,那么字符串"(X)"的深度是x+1
参考：https://gitee.com/SnailClimb/JavaGuide/blob/master/docs/dataStructures-algorithms
示例：
输入描述:
输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。
输出描述:
输出一个正整数,即这个序列的深度。
--------------------------------------------------------------------
输入:
(())
输出:
2
思路：遍历字符串，维护一个变量count记录深度。遇到（，则count+1，否则count - 1。
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int count = 0, max = 0;
for (char ch : s.toCharArray()) {
if (ch == '(')
count++;
else
count--;
max = Math.max(count, max);
}
sc.close();
System.out.println(max);
}
}
4.最长有效括号（32-难）
题目描述：给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
思路：对于括号匹配问题一般使用栈进行判断，栈中存放左括号的下标，便于计算最大长度：
- 入栈操作：遇到
(，将其下标入栈，等待匹配；注意：为了避免栈为空报错：开始压入-1，过程中用一个右括号下标作为标志。 - 出栈操作：遇到
)，出栈更新最大长度。
另外，官方给出了一种不需要额外空间的解法，维持两个计数器left和right：
- 遍历字符串，遇到左括号，left增加，否则right增加，当left == right时，计算此时长度。
- 当right > left时，我们开始，即left和right置0。
-
注意：但是对于
(()，左括号一直大于右括号，我们没法得到最大长度，即left == right，其实，我们只需要倒序再遍历一遍即可。
代码：
// 辅助栈
public int longestValidParentheses(String s) {
Deque<Integer> stack = new LinkedList<>();
if (s == null || s.length() == 0) {
return 0;
}
int ans = 0;
stack.push(-1); // 避免开始即为右括号
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
ans = Math.max(ans, i - stack.peek());
}
}
}
return ans;
}
// 遍历计数
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int ans = 0;
int left = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
ans = Math.max(ans, left + right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
ans = Math.max(ans, left + right);
} else if (left > right) {
left = right = 0;
}
}
return ans;
}
5.有效的括号字符串（678-中）
题目描述：给定一个只包含三种字符的字符串：（，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 左右括号必须匹配，左括号在前，右括号在后
- *可以为单个左右括号或者一个空格
- 空字符串有效
示例：
输入: "(*)"
输出: True
输入: "(*))"
输出: True
思路：基本匹配问题，想到使用栈，关键是如何处理*问题：使用双栈，但是栈中存的是下标，为什么呢？当我们遍历完字符串时，如果两栈中都还有元素，那么我们就可以比较下标判断是否可以构成有效括号，比如 *( 就不可以。
- 遇到左括号和星号，入栈对应下标
- 遇到有括号，优先使用left栈中字符，如果没有，使用star栈中星号进行匹配
- 解决栈中剩余元素下标，最终左括号栈为空返回true（即全部匹配成功）
还有一种类似最长有效括号，使用计数法，正反两遍，判断多余左括号的情况。代码如下。
代码：
// 辅助栈
public boolean checkValidString(String s) {
Deque<Integer> leftStack = new LinkedList<>();
Deque<Integer> starStack = new LinkedList<>();
if (s == null || s.length() == 0) {
return true;
}
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '(') {
leftStack.push(i);
} else if (s.charAt(i) == '*') {
starStack.push(i);
} else {
if (leftStack.isEmpty() && starStack.isEmpty()) {
return false;
} else if (!leftStack.isEmpty()) {
leftStack.pop();
} else {
starStack.pop();
}
}
}
while (!leftStack.isEmpty() && !starStack.isEmpty()) {
if (leftStack.peek() > starStack.peek()) {
return false;
}
leftStack.pop();
starStack.pop();
}
return leftStack.isEmpty();
}
// 计数法
public boolean checkValidString(String s) {
int countL = 0, countLS = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == '(') {
countL++;
} else if (s.charAt(i) == '*') {
countLS++;
} else {
if (countL > 0) {
countL--;
} else if (countLS > 0) {
countLS--;
} else {
return false;
}
}
}
int countR = 0, countRS = 0;
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == ')') {
countR++;
} else if (s.charAt(i) == '*') {
countRS++;
} else {
if (countR > 0) {
countR--;
} else if (countRS > 0) {
countRS--;
} else {
return false;
}
}
}
return true;
}
6.删除无效括号（301-中）
题目描述：给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
思路：一般对于括号的有效性，一般使用栈和计数法（）。本题使用dfs+计数法：
- 提前确定dfs计数得分的可能最大值（便于确定边界）
- 对于枚举括号类型，在不越界的情况下，括号可以选择加或者不加
- 根据题意，一般类型选择直接加入结果
- 结果set去重：遍历数组结束，查看得分（score == 0保存这个结果，并更新dfs最大子串的长度），不满足则直接return
- 最终根据全局变量len,统计最终的结果
代码：
class Solution {
// 记录dfs过程中最大的子串
private int len = 0;
public List<String> removeInvalidParentheses(String s) {
// 对结果进行去重
Set<String> all = new HashSet<>();
char[] chs = s.toCharArray();
int l = 0, r = 0;
for (char c : chs) {
if (c == '(') {
l++;
} else if (c == ')'){
r++;
}
}
// 提前dfs可能的最大结果
int max = Math.min(l, r);
dfs(chs, 0, 0, max, "", all);
List<String> ans = new ArrayList<>();
for (String str : all) {
// 挑选符合要求的结果
if (str.length() == len) {
ans.add(str);
}
}
return ans;
}
private void dfs(char[] chs, int i, int score, int max, String cur, Set<String> ans) {
if (i == chs.length) {
if (score == 0 && cur.length() >= len) {
// 找到合法的括号组合，加入结果集
len = Math.max(len, cur.length());
ans.add(cur);
}
return;
}
if (chs[i] == '(') {
// 通过得分，检查左括号不越界（加或者不加）
if (score + 1 <= max) {
dfs(chs, i + 1, score + 1, max, cur + "(", ans);
}
dfs(chs, i + 1, score, max, cur, ans);
} else if (chs[i] == ')') {
// 通过得分，检查右括号不越界（加或者不加）
if (score > 0) {
dfs(chs, i + 1, score - 1, max, cur + ")", ans);
}
dfs(chs, i + 1, score, max, cur, ans);
} else {
// 一般字符直接加入结果
dfs(chs, i + 1, score, max, cur + String.valueOf(chs[i]), ans);
}
}
}
