Valid Parentheses

问题描述

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

The brackets must close in the correct order,"()"and"()[]{}"are all valid but"(]"and"([)]"are not.

题目链接

https://leetcode.com/problems/valid-parentheses/#/description

Python

利用字典结构,kv的可以同时取到,效率不高,但是代码简洁

class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []

Java

public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
stack.push(s.charAt(i));
else if (stack.empty()) {
return false;
} else {
if (!isPair(stack.pop(), s.charAt(i))) return false;
}
}
return stack.empty();
}
public boolean isPair(char a, char b) {
if (a == '(' && b == ')') return true;
if (a == '[' && b == ']') return true;
if (a == '{' && b == '}') return true;
return false;
}
}