class Solution {
public:
bool isValid(string s) {
}
};
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104s 仅由括号 '()[]{}' 组成原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2022-08-31 10:02:50
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
pairs = {
")": "(",
"]": "[",
"}": "{",
}
stack = list()
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2021-07-21 09:54:44
func isValid(s string) bool {
stack := []rune{}
l := 0
for _, c := range s {
if c == '(' || c == '[' || c == '{' {
stack = append(stack, c)
} else {
l = len(stack)
if l == 0 {
return false
}
last := stack[l-1]
if (last == '(' && c != ')') || (last == '[' && c != ']') || (last == '{' && c != '}') {
return false
}
stack = stack[:l-1]
}
}
return len(stack) == 0
}
java 解法, 执行用时: 14 ms, 内存消耗: N/A, 提交时间: 2018-08-28 13:38:48
class Solution {
public boolean isValid(String s) {
if ( "".equals(s) )
return true;
Stack<Character> stack = new Stack<Character>();
char[] chrs = s.toCharArray();
for (char c : chrs) {
if ( '{' == c || '[' == c || '(' == c ) {
stack.push(c);
} else if ( '}' == c || ']' == c || ')' == c ) {
if ( stack.empty() || c == '}' && stack.peek() != '{' || c == ']' && stack.peek() != '[' || c == ')' && stack.peek() != '(' ) {
return false;
} else {
stack.pop();
}
}
}
return stack.empty();
}
}