20. Valid Parentheses
Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
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) Java
class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}
Deque<Character> q = new LinkedList<>();
char[] chars = s.toCharArray();
for (char c : chars) {
if (c == '(') {
q.push(')');
}else if (c == '{') {
q.push('}');
} else if (c == '[') {
q.push(']');
} else if (q.isEmpty() || c != q.pop()) {
return false;
}
}
return q.size() == 0;
}
}
(2) Python
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for c in s:
if c == '[':
stack.append(']')
elif c == '{':
stack.append('}')
elif c == '(':
stack.append(')')
elif not stack or stack.pop() != c:
return False
return not stack
(3) Scala
object Solution {
def isValid(s: String): Boolean = {
s match {
case null => return true
case _ => {
var sk = scala.collection.mutable.Stack[Character]()
for (c <- s) {
if (c == '(') {
sk.push(')')
} else if (c == '{') {
sk.push('}')
} else if (c == '[') {
sk.push(']')
} else if (sk.isEmpty || sk.pop() != c) {
return false
}
}
return sk.isEmpty
}
}
}
}