20. Valid Parentheses

Easy (Dễ) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)Stack (Ngăn xếp)Union Find (Tập hợp rời rạc)String (Chuỗi)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0020-valid-parentheses.cpp 
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int n = s.size();
        unordered_map<char, char> um;
        um['('] = ')';
        um['['] = ']';
        um['{'] = '}';

        for (int i = 0; i < n; ++i) {
            if (um.find(s[i]) != um.end()) {
                st.push(s[i]);
            }
            else {
                if (st.empty()) {
                    return false;
                }
                char topSt = um[st.top()];
                st.pop();
                if (topSt != s[i]) {
                    return false;
                }
            }
        }
        return st.empty();
    }
};
Python 0020-valid-parentheses.py 
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        hashMap = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        
        for char in s:
            if char in hashMap:
                stack.append(char)
            else:
                if len(stack):
                    key = stack.pop()
                    if hashMap[key] != char:
                        return False
                elif len(stack) == 0:
                    return False
                
        return len(stack) == 0