赞
踩
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
注意:空字符串可被认为是有效字符串。
输入: "()"`在这里插入代码片`
输出: true
输入: "()[]{}"
输出: true
输入: "(]"
输出: false
输入: "([)]"
输出: false
输入: "{[]}"
输出: true
看到这个题目,应该联想到栈
首先遍历这个字符串的每个元素c,
如果 c 是左边括号,那么就让与该括号相对于的右边括号入栈
如果 c 是右边括号,就判断 c 是否与刚才入栈的元素相同
- 如果相同,代表匹配成功
- 如果不相同,代表匹配不成功
注意:一个特殊情况,如果遍历到的字符是右括号,
但是栈这个时候为空,该怎么办?
这种情况下,遍历完s字符串,遇到第一个元素不会进栈,
这个时候判断stack是否为0,如果为0返回false
遍历完 s 字符串,看stack是否为空
—如果为空,代表 s 匹配成功
—如果不为空,代表 s 匹配不成功
class Solution { public boolean isValid(String s) { if(s == null) { return true; } //定义一个栈 Stack<Character> stack = new Stack<>(); //遍历字符串 s for(char c : s.toCharArray()) { if(c=='(')stack.push(')'); else if(c=='[')stack.push(']'); else if(c=='{')stack.push('}'); else { if(stack.isEmpty() || stack.pop() != c) { return false; } } } return stack.isEmpty(); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。