力扣链接：20. 有效的括号，难度：简单。
给定一个只包括 (，)，{，}，[，] 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入: s = "()"
输出: true
示例 2:
输入: s = "()[]{}"
输出: true
示例 3:
输入: s = "(]"
输出: false
示例 4:
输入: s = "([])"
输出: true
约束:
1 <= s.length <= 10000s仅由括号()[]{}组成
提示 1
Use a stack of characters.
提示 2
When you encounter an opening bracket, push it to the top of the stack.
提示 3
When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.
思路
- 括号匹配关注的主要是
前一个字符与当前字符。有两种情况要考虑：- 如果
当前字符是左括号，则不需要匹配，直接保存起来。 - 如果
当前字符是右括号，并且前一个字符与当前字符配成了一对，则这两个字符都可以消失了；反之，如果配对失败，直接返回false。
- 如果
- 这种关注
前一个字符与当前字符的场景，适合用栈实现。 - 左右括号之间的对应关系可以保存在一个
Map中。 - 最后，如果栈为空，说明全部配对成功，返回
true；否则返回false。
复杂度
时间复杂度
O(N)
空间复杂度
O(N)
JavaScript #
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
const closeToOpen = new Map([
[')', '('],
['}', '{'],
[']', '['],
])
const stack = []
for (const char of s) {
if (!closeToOpen.has(char)) {
// is open bracket
stack.push(char)
continue
}
// is close bracket
if (stack.length === 0) {
return false
}
// stack top value doesn't match the expected value
if (stack.pop() != closeToOpen.get(char)) {
return false
}
}
return stack.length === 0
};
Python #
class Solution:
def isValid(self, s: str) -> bool:
# Map closing brackets to their opening brackets
close_to_open = {
')': '(',
'}': '{',
']': '[',
}
stack = []
for char in s:
if char not in close_to_open:
# is open bracket
stack.append(char)
continue
# is close bracket
if not stack:
return False
# stack top value doesn't match the expected value
if stack.pop() != close_to_open[char]:
return False
return not stack
Java #
class Solution {
public boolean isValid(String s) {
// Map closing brackets to their opening brackets
var closeToOpen = new HashMap<Character, Character>();
closeToOpen.put(')', '(');
closeToOpen.put('}', '{');
closeToOpen.put(']', '[');
var stack = new Stack<Character>();
for (char c : s.toCharArray()) {
if (!closeToOpen.containsKey(c)) {
// is open bracket
stack.push(c);
continue;
}
// is close bracket
if (stack.isEmpty()) {
return false;
}
// stack top value doesn't match the expected value
if (stack.pop() != closeToOpen.get(c)) {
return false;
}
}
return stack.isEmpty();
}
}
C++ #
class Solution {
public:
bool isValid(string s) {
// Map closing brackets to their opening brackets
unordered_map<char, char> closeToOpen = {
{')', '('},
{'}', '{'},
{']', '['}
};
stack<char> st;
for (char c : s) {
if (closeToOpen.find(c) == closeToOpen.end()) {
// is open bracket
st.push(c);
continue;
}
// is close bracket
if (st.empty()) {
return false;
}
// stack top value doesn't match the expected value
if (st.top() != closeToOpen[c]) {
return false;
}
st.pop();
}
return st.empty();
}
};
C# #
public class Solution
{
public bool IsValid(string s)
{
// Map closing brackets to their opening brackets
var closeToOpen = new Dictionary<char, char>()
{
{')', '('},
{'}', '{'},
{']', '['}
};
var stack = new Stack<char>();
foreach (char c in s) {
if (!closeToOpen.ContainsKey(c))
{
// is open bracket
stack.Push(c);
continue;
}
// is close bracket
if (stack.Count == 0)
{
return false;
}
// stack top value doesn't match the expected value
if (stack.Pop() != closeToOpen[c])
{
return false;
}
}
return stack.Count == 0;
}
}
Go #
func isValid(s string) bool {
// Map closing brackets to their opening brackets
closeToOpen := map[rune]rune{
')': '(',
'}': '{',
']': '[',
}
stack := []rune{}
for _, char := range s {
if _, isClose := closeToOpen[char]; !isClose {
// is open bracket
stack = append(stack, char)
continue
}
// is close bracket
if len(stack) == 0 {
return false
}
lastChar := stack[len(stack) - 1]
// stack top value doesn't match the expected value
if lastChar != closeToOpen[char] {
return false
}
stack = stack[:len(stack) - 1] // pop operation
}
return len(stack) == 0
}
Ruby #
# @param {String} s
# @return {Boolean}
def is_valid(s)
# Map closing brackets to their opening brackets
close_to_open = {
')' => '(',
'}' => '{',
']' => '['
}
stack = []
s.each_char do |char|
if !close_to_open.key?(char)
# is open bracket
stack.push(char)
next
end
# is close bracket
if stack.empty?
return false
end
# stack top value doesn't match the expected value
if stack.pop != close_to_open[char]
return false
end
end
stack.empty?
end