题目:四数之和
要求:给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
例如 :
输入:"()" "()[]{}" "(]" "([)]"
输出:true true false false
解题思路:
- 对于有效的括号,总是成对出现,且左括号必须先于右括号出现
- 对于案例"()[]{}"分析,其中的“(”在第一位,")"在最后一位,也就是说,对括号的匹配有先后顺序,且对于“([{”,来说,总是先进先出,故可以使用栈来辅助匹配的实现,每个右括号前必须有左括号与之匹配。
- 在栈中,如果栈的长度大于s长度的二分之一,即可以视为不匹配,因为匹配到最后总会有多余的符号无法匹配。
- 同理,如果s的长度为奇数,尽管绝大多数的括号可以匹配,但至少会有一个括号是无法匹配的
题解代码如下:
class Solution {
public boolean isValid(String s) {
if (null == s || s.length() % 2 == 1) {
return false;
}
if (s.startsWith(")") || s.startsWith("]") || s.startsWith("}")) {
return false;
}
char[] chars = s.toCharArray();
int len = chars.length;
Stack<Character> stack = new Stack<>();
for (char aChar : chars) {
if ('(' == aChar) {
stack.push(')');
} else if ('[' == aChar) {
stack.push(']');
} else if ('{' == aChar) {
stack.push('}');
} else if (stack.isEmpty() || aChar != stack.pop()) {
return false;
}
if (stack.size() > len / 2) {
return false;
}
}
return stack.isEmpty();
}
}