每天一题LeetCode【第17天】
2017-02-06 本文已影响94人
草稿纸反面
T20. Valid Parentheses【Easy】
题目
给定一个只包含字符'(',')','{','}','['和']'的字符串,确定输入字符串是否是有效的。
括号必须正确匹配,比如“()”和“()[] {}”都有效,但“(]”和“([]]”不是。
例如,
给出链表: 1->2->3->4->5,以及 n = 2.
在移除了倒数第二个节点后, 链表变成了 1->2->3->5.
补充:
给出的 n 总是有效地
尝试把这题一遍过
思路
① 首先建议了解一下栈(先进后出的数据结构,类比桶装容器)
② 把识别左边的括号把对应的右边的括号放入栈中
③ 没有左边了以后从栈中 pop 出括号和下一子比较是否相同,若不相同或者栈空了代表错了
④ 总的思想就是 ② ③ 两步的操作,具体看代码就好~
⑤ 有问题欢迎吐槽~
代码
代码取自 Top Solution,稍作注释
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
// 把识别左边的括号把对应的右边的括号放入栈中
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
//没有左边了以后从栈中 pop 出括号和下一子比较是否相同,若不相同或者栈空了代表错了
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
//如果一直没错并且栈空了就代表是有效的
return stack.isEmpty();
}
补充
这种括号匹配的题一般的通常想法就是栈吧(这算什么补充)~