[TOC]
Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.
An input string is valid if:
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: trueExample 2:
Input: "()[]{}"
Output: trueExample 3:
Input: "(]"
Output: falseExample 4:
Input: "([)]"
Output: falseExample 5:
Input: "{[]}"
Output: trueclass Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.empty()) {
return false;
}
char topChar = stack.pop();
if (c == ')' && topChar != '(') {
return false;
}
if (c == ']' && topChar != '[') {
return false;
}
if (c == '}' && topChar != '{') {
return false;
}
}
}
return stack.isEmpty();
}
}Runtime:?15 ms
class Solution {
public boolean isValid(String s) {
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.isEmpty() || c != stack.pop()) {
return false;
}
}
return stack.isEmpty();
}
}Runtime:?12 ms
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = list()
dict = {'(': ')', '[': ']', '{': '}'}
for c in s:
if c in dict.keys():
stack.append(dict[c])
elif c in dict.values():
if len(stack) == 0 or c != stack.pop():
return False
else:
False
return len(stack) == 0Runtime:?40 ms
原文：https://www.cnblogs.com/xugenpeng/p/9192495.html