已知一个字符串都是由左括号(和右括号)组成,判断该字符串是否是有效的括号组合。
程序员文章站
2022-07-16 10:18:24
...
题目:已知一个字符串都是由左括号(和右括号)组成,判断该字符串是否是有效的括号组合。
例子:
()()() 返回true
())() false
根据观察
遍历的过程中,当右括号数大于左括号数,直接返回false
遍历结束时 :1.当左括号数等于右括号数 返回true
2.当左括号数大于右括号数 返回false
方法一 定义一个变量记录遍历过程
int count 当遇到左括号数count++ 当遇到右括号数 count–
在遍历时,只要count<0 时, 直接返回false
遍历结束后 count == 0 返回true . 否者左括号数不等右括号数(即返回false)
代码如下
public static boolean isValid(String s) {
if (s == null || s.length() == 0) return true;
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
count++;
} else if (s.charAt(i) == ')' && --count < 0) {
return false; //表示右括号数大于左括号数
}
}
return count == 0;
}
//时间复杂度O(n) 空间复杂度O(1)
*方法二 * 用栈来解决 时间复杂度O(n) 空间复杂度O(n)
与(Leetcode20)类似
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
public static boolean isValid(String s) {
if (s.length() == 0) return true;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') stack.push(c);
if (c == ')' || c == '}' || c == ']') {
if (stack.isEmpty()) return false;
char one = stack.pop();
if (c == ')' && one != '(') return false;
if (c == ']' && one != '[') return false;
if (c == '}' && one != '{') return false;
}
}
if (!stack.isEmpty()) return false;
return true;
}
进阶
Leetcode 32
给定一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”`
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0) return 0;
int dp[] = new int[s.length()];
int res = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
int left = i - dp[i - 1] - 1;
if (left >= 0 && s.charAt(left) == '(') {
dp[i] = dp[i - 1] + 2 + (left > 0 ? dp[left - 1] : 0);
}
res = Math.max(res, dp[i]);
}
}
return res;
}
`
上一篇: 91. 解码方法
下一篇: P1049 装箱问题