【LeetCode】括号（有效括号、括号生成、最长有效括号······）
【LeetCode】括号（有效括号、括号生成、最长有效括号······）
括号★★
【题目】括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
【示例】
输入：n = 3
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
【解题思路】使用递归来生成括号
-
若在生成过程中右括号数量大于左括号数量则终止递归，或者左括号超过限定数目
n则终止递归 -
若左括号等于右括号等于
n，则添加至结果集并且终止递归
class Solution {
List<String> res;
public List<String> generateParenthesis(int n) {
res = new ArrayList<String>();
helper("", n, n);
return res;
}
private void helper(String str, int le, int ri) {
if(le > ri || le < 0) return;
if(le == 0 && ri == 0) {
res.add(new String(str));
return;
}
helper(str + "(", le - 1, ri);
helper(str + ")", le, ri - 1);
}
}
有效的括号★
【题目】给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串
【示例】
----输入: "()[]{}"
输出: true
----输入: "([)]"
输出: false
【解题思路】
方法一：使用栈模拟，遍历字符串
- 若为左括号则入栈
- 若为右括号则判断栈顶元素，若栈为空则返回
false，若栈顶元素是与之对应的左括号则出栈，否则返回false - 最后若栈为空，则返回
true，否则返回false
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for(char c : s.toCharArray()) {
if(c == '(' || c == '[' || c == '{') {
stack.push(c);
}else if(!stack.isEmpty()){
if(c == ')' && stack.peek() == '(' ||
c == ']' && stack.peek() == '[' ||
c == '}' && stack.peek() == '{') {
stack.pop();
}else {
return false;
}
}else {
return false;
}
}
return stack.isEmpty();
}
}
方法二：使用String类的函数，用""替换所有的()[]{}，最后判断字符串是否为空即可
class Solution {
public boolean isValid(String s) {
while(!s.equals("")) {
String str = s.replace("()", "").replace("[]", "").replace("{}", "");
if(str.equals(s)) return false;
s = str;
}
return true;
}
}
最长有效括号★★★
【题目】给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
【示例】
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
【解题思路】使用栈保存左括号下标，栈初始化为（-1）
- 对于左括号，入栈对应下标
- 对于右括号，出栈一个下标（表示出栈下标对应的左括号对应当前右括号）
- 若栈为空，则说明不能构成有效括号，入栈当前下标（
已遍历最右端不能构成有效括号的下标） - 若栈不为空，则说明出栈下标对应为有效括号，更新
res = Math.max(res, i - stack.peek())
- 若栈为空，则说明不能构成有效括号，入栈当前下标（
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int res = 0;
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 {
res = Math.max(res, i - stack.peek());
}
}
}
return res;
}
}
有效的括号字符串★★
【题目】给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号
(必须有相应的右括号) - 任何右括号
)必须有相应的左括号( - 左括号
(必须在对应的右括号之前)
-
*可以被视为单个右括号)，或单个左括号(，或一个空字符串 - 一个空字符串也被视为有效字符串
**注意:**字符串大小将在 [1，100] 范围内。
【示例】
---输入: "()"
输出: True
---输入: "(*))"
输出: True
【解题思路】
方法一：双栈模拟，栈left保存左括号下标，栈star保存*下标，遍历字符串
- 若当前字符为
（，则将下标i进栈left - 若当前字符为
*，则将其下标i进栈start - 若当前字符为
），若left不为空，优先配对出栈；若left为空且star不为空，则star出栈（表示当前出栈的下标处*可以表示一个左括号）；若left和star均为空，则没有与其配对的，返回false
然后再来看left和star中元素，此时表示*代替右括号来配对left栈中剩余的左括号
- 若
left栈顶元素大于star栈顶元素，表示*下标处于左括号下标左边，返回false - 否则均出栈一个元素，表示配对
最后若left不为空，表示剩余左括号无法配对，返回false，若为空，返回true
class Solution {
public boolean checkValidString(String s) {
Stack<Integer> left = new Stack<Integer>();
Stack<Integer> star = new Stack<Integer>();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c == '(') {
left.push(i);
}else if(c == '*') {
star.push(i);
}else {
if(!left.isEmpty()) {
left.pop();
}else if(!star.isEmpty()) {
star.pop();
}else {
return false;
}
}
}
while(!left.isEmpty() && !star.isEmpty()) {
if(left.pop() > star.pop()) return false;
}
return left.isEmpty();
}
}
方法二：使用两个变量lo和hi分别表示未匹配左括号的上界和下界
class Solution {
public boolean checkValidString(String s) {
int lo = 0, hi = 0; //未匹配左括号数量的范围
for(char c : s.toCharArray()) {
if(c == '(') {
lo++;
hi++;
}else if(c == ')') {
lo = Math.max(0, lo - 1);
hi--;
if(hi < 0) return false; //右括号多于左括号且不能匹配
}else {
lo = Math.max(0, lo - 1);
hi++;
}
}
return lo == 0;
}
}
使括号有效的最少添加★★
【题目】给定一个由 ‘(’ 和 ‘)’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(’ 或是 ‘)’，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
- 它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
【示例】
---输入："((("
输出：3
---输入："()))(("
输出：4
【解题思路】最少添加至每个括号刚好匹配，即补充括号使不匹配的括号匹配
方法一：遍历统计，使用countLeft标记左括号的个数，leastAdd记录添加个数
- 若为左括号，则
countLeft++ - 若为右括号，若
countLeft值大于0，则表示当前右括号有相应左括号与其配对，若countLeft值等于0，则表示没有与之对应的左括号配对，即需要添加一个（leastAdd++）
最后返回leastAdd + countLeft，此时countLeft表示没有与之配对的右括号的数量
class Solution {
public int minAddToMakeValid(String S) {
int countLeft = 0; //标记左括号的个数
int leastAdd = 0; //最少添加个数
for(char c : S.toCharArray()){
if(c == '(') {
countLeft++;
}else {
if(countLeft == 0) {
leastAdd++;
}else {
countLeft--;
}
}
}
return leastAdd + countLeft;
}
}
方法二：使用空字符串替换所有的()，最后剩余字符串的长度就是其未匹配的括号数量
class Solution {
public int minAddToMakeValid(String S) {
while(S.contains("()")) {
S = S.replace("()", "");
}
return S.length();
}
}
有效括号的嵌套深度★★
【题目】有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末**「嵌套深度」**部分。
有效括号字符串类型与对应的嵌套深度计算方法如下图所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hyBBnVS8-1610270685893)(…\LeetCode\great\有效括号嵌套深度.png)]
给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。
- 不相交：每个 seq[i] 只能分给
A和B二者中的一个，不能既属于A也属于B。 -
A或B中的元素在原字符串中可以不连续。 A.length + B.length = seq.length- 深度最小：
max(depth(A), depth(B))的可能取值最小。
划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：
-
answer[i] = 0，seq[i]分给A。 -
answer[i] = 1，seq[i]分给B。
如果存在多个满足要求的答案，只需返回其中任意 一个 即可。
【示例】
----输入：seq = "(()())"
输出：[0,1,1,1,1,0]
----输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1
【解题思路】
对于示例：( ( ) ( ( ) ) ( ) )
嵌套深度：1 2 2 2 3 3 2 2 2 1
分配方案：A B B B A A B B B A
可见奇数的嵌套深度分配给A，偶数的嵌套深度分配给B
class Solution {
public int[] maxDepthAfterSplit(String seq) {
int[] res = new int[seq.length()];
int deep = 0;
for(int i = 0; i < seq.length(); i++) {
if(seq.charAt(i) == '(') {
deep++;
res[i] = deep & 1;
}else {
res[i] = deep & 1;
deep--;
}
}
return res;
}
}