20. Valid Parentheses
給定一個僅包含字符 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，判斷輸入字符串是否有效。
當輸入字符串符合以下條件時，字符串是有效的：開括號必須由相同類型的括號關閉。
開括號必須以正確的順序關閉。
每個閉括號都有一個對應的相同類型的開括號。
範例 1：
輸入：s = "()" 輸出：true
Python
class Solution:
def isValid(self, s: str) -> bool:
# Dictionary to hold the mappings of open and close brackets
bracket_map = {')': '(', '}': '{', ']': '['}
# Stack to keep track of opening brackets
stack = []
# Iterate through each character in the string
for char in s:
# If the character is a closing bracket
if char in bracket_map:
# Pop the topmost element from the stack if it is not empty,
otherwise assign a dummy value
top_element = stack.pop() if stack else '#'
# Check if the popped element matches the corresponding opening
bracket
if bracket_map[char] != top_element:
return False
else:
# If it's an opening bracket, push it onto the stack
stack.append(char)
# Return True if the stack is empty (all brackets are matched)
return not stack
16.54MB, 29ms
C++
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isValid(string s) {
// Map to hold the mappings of open and close brackets
unordered_map<char, char> bracketMap = {
{')', '('},
{'}', '{'},
{']', '['}
};
// Stack to keep track of opening brackets
stack<char> stack;
// Iterate through each character in the string
for (char& c : s) {
// If the character is a closing bracket
if (bracketMap.find(c) != bracketMap.end()) {
// Pop the topmost element from the stack if it is not empty, otherwise
assign a dummy value
char topElement = stack.empty() ? '#' : stack.top();
stack.pop();
// Check if the popped element matches the corresponding opening bracket
if (bracketMap[c] != topElement) {
return false;
}
} else {
// If it's an opening bracket, push it onto the stack
stack.push(c);
}
}
// Return true if the stack is empty (all brackets are matched)
return stack.empty();
}
};
8.04MB, 3ms
Javascript
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
// Map to hold the mappings of open and close brackets
const bracketMap = {
')': '(',
'}': '{',
']': '['
};
// Stack to keep track of opening brackets
const stack = [];
// Iterate through each character in the string
for (const char of s) {
// If the character is a closing bracket
if (bracketMap[char]) {
// Pop the topmost element from the stack if it is not empty, otherwise
assign a dummy value
const topElement = stack.length ? stack.pop() : '#';
// Check if the popped element matches the corresponding opening bracket
if (bracketMap[char] !== topElement) {
return false;
}
} else {
// If it's an opening bracket, push it onto the stack
stack.push(char);
}
}
// Return true if the stack is empty (all brackets are matched)
return stack.length === 0;
};
49.48MB, 52ms
