给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
输入:s = "(]"
输出:false
public static boolean isVaild(String s) {
// 输入的 s 字符串长度为奇数或第一项是右括号直接 false
if (s.length() % 2 != 0)
return false;
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.empty() || c != stack.pop())
return false;
}
return stack.empty();
}
巧法 forEach遍历每个字符; 如果存在左边括号; 则使用栈的方式存储对应的右边括号,成为待匹配的右括号,等待下一轮循环进来与 c 比较同时 pop(); (就巧在这次比较,如果 c 为右括号,执行
else if (stack.empty() || c != stack.pop()) return false;
最后若栈为空,则一定是正确的括号
LeetCode地址—>20. 有效的括号