LeetCode 20. Valid Parentheses (Easy)

Posted by Jfson on 2018-12-21

Stack

视频讲解地址

LeetCode 20. Valid Parentheses (Easy)

Given a string containing just the characters ‘(’,’)’,’{’,’}’,’[’ and ’]’,determine if the input string is valid.
An input string is valid if:

1.Open brackets must be closed by the same type of brackets.
2.Open brackets must be closed in correct order.

题意:判断输入是否合法,类似于代码中括号合法检测。需要满足以下的test类型。

1
2
3
4
5
6
Note that an empty string is also considered valid.
Example 1: Input: “()” Output: true
Example 2: Input: “()[]{}” Output: true
Example 3: Input: “(]” Output: false
Example 4: Input: “()[)]” Output: false
Example 5: Input: “{[]}” Output: true
  • Solution 1:四个if (error不可行)
  • Solution 2:计数 (error不可行) ()()()[(])
  • Solution 3:Stack () ,利用栈,后进先出的特性,对需入栈的元素跟栈顶元素比较,相匹配的进行移除栈操作,最后栈为空,则合法。
  • 题解: image
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
Stack stack = new Stack();
for(int i = 0;i<s.length;i++) {
if(map.containtsKey(s.charAt(i))){ // end with
Character top = stack.empty() ? "*" : statck.pop(); //remove
if(top != map.get(s.charAt(i))){
return false;
}
}else{
stack.push(s.charAt(i));
}
}
return stack.empty();
}
}

pv UV: