Problem
Given a string 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.
Note that an empty string is also considered valid.
Example 1:
Input: "()" Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]" Output: false
Example 4:
Input: "([)]" Output: false
Example 5:
Input: "{[]}"
Output: true
Solution: Stack
Using a stack to track the existing open parentheses, if the current one is a close parenthesis but does not match the top of the stack, return false, otherwise pop the stack. Check whether the stack is empty in the end.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 0 ms class Solution { public: bool isValid(string s) { map<char, char> p{{')', '('}, {']', '['}, {'}', '{'}}; stack<char> st; for (char c : s) { if (!p.count(c)) { st.push(c); } else { if (st.empty() || p[c] != st.top()) return false; st.pop(); } } return st.empty(); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# Author: Huahua class Solution: def isValid(self, s): p = {')' : '(', ']': '[', '}' : '{'} stack = [] for c in s: if c not in p: stack.append(c) else: if not stack or stack[-1] != p[c]: return False stack.pop() return not stack |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment