20. 有效的括号(Valid Parentheses)E
英文题目
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}" Output: true
Example 3:
Input: s = "(]" Output: false
Example 4:
Input: s = "([)]" Output: false
Example 5:
Input: s = "{[]}" Output: true
Constraints:
1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.
中文题目
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
示例 4:
输入:s = "([)]" 输出:false
示例 5:
输入:s = "{[]}" 输出:true
提示:
1 <= s.length <= 10^4
s 仅由括号 '()[]{}' 组成
栈
栈内存储的都是左边的括号,遍历字符串,遇到左边的括号存放在栈内,遇到右边的括号时,栈不能为空,并取出栈顶元素对应的右括号,判断和当前字符是否相等
预先把对应匹配的括号对记录下来,可以有效减少硬编码和if分支
时间复杂度O(n),n 是字符串的长度,空间复杂度,其中表示字符集,本题中只包含 6 种括号
# python: 时间 32 ms, 击败 95.96%; 内存 14.8 MB, 击败 78.40% class Solution: def isValid(self, s: str) -> bool: if len(s) % 2 == 1: return False pair = {'(':')', '{':'}', '[':']'} stack = [] for c in s: if c in pair: stack.append(c) else: # 注意有栈是空以及不匹配两种情况 if not stack or c != pair[stack.pop()]: return False return True if not stack else False
// c++: 时间 0 ms, 击败 100%; 内存 6.2 MB, 击败 33.79% class Solution { public: bool isValid(string s) { if (s.size() % 2 == 1) { return false; } // map 的写法注意下 unordered_map<char, char> pair { {'(', ')'}, {'[', ']'}, {'{', '}'} }; stack<char> st; for (const char c: s) { // 此处也可 if (pairs.count(c) == 1) 替代 // count 的作用是在map中找到key的数量,返回要么是 1 要么是 0 if (pair.find(c) != pair.end()) { st.push(c); } else { // 注意栈取栈顶和弹出的语法 if (st.empty() || c != pair[st.top()]) { return false; } st.pop(); } } return st.empty() ? true : false; } };
// java: 时间 2 ms, 击败 49.66%; 内存 39.7 MB, 击败 29.54% class Solution { public boolean isValid(String s) { if (s.length() % 2 == 1) { return false; } Map<Character, Character> pair = new HashMap<>() {{ put('(', ')'); put('[', ']'); put('{', '}'); }}; Deque<Character> stack = new LinkedList<>(); for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); if (pair.containsKey(c)) { stack.push(c); } else { if (stack.isEmpty() || c != pair.get(stack.peek())) { return false; } stack.pop(); } } return stack.isEmpty(); } }
// go: 时间 4 ms, 击败 14.60%; 内存 1.9 MB, 击败 79.90% func isValid(s string) bool { if len(s) % 2 == 1 { return false } pair := map[byte]byte { '(': ')', '[': ']', '{': '}', } stack := []byte{} for i := 0; i < len(s); i++ { c := s[i] if _, ok := pair[c]; ok { stack = append(stack, c) } else { if len(stack) == 0 || c != pair[stack[len(stack)-1]] { return false } stack = stack[:len(stack)-1] } } return len(stack) == 0 }
// go: 时间 0 ms, 击败 100%; 内存 1.9 MB, 击败 49.11% func isValid(s string) bool { if len(s) % 2 == 1 { return false } pair := map[rune]rune { '(': ')', '[': ']', '{': '}', } stack := []rune{} for _, c := range s { if _, ok := pair[c]; ok { stack = append(stack, c) } else { if len(stack) == 0 || c != pair[stack[len(stack)-1]] { return false } stack = stack[:len(stack)-1] } } return len(stack) == 0 }
// javascript: 时间 64 ms, 击败 74.50%; 内存 41.6 MB, 击败 49.83% /** * @param {string} s * @return {boolean} */ var isValid = function(s) { if (s.length % 2 == 1) { return false; } const pair = new Map([ ['(', ')'], ['[', ']'], ['{', '}'] ]); const stack = []; for (let c of s) { if (pair.has(c)) { stack.push(c); } else { if (!stack.length || c != pair.get(stack.pop())) { return false; } } } return !stack.length; };