🌱 Keegan's Digital Garden

20. Valid Parentheses

3 min read

📝 Problem Details

🔍 Problem Understanding

Given a string of brackets, we want to return if the string is ‘valid’ or not. There are 3 rules pertaining to a string’s validity:

  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.

🎯 Key Insights

- the opening bracket on the outside, must be closed last if there are other open brackets nested inside it

🔑 Approach

1. Use a stack to keep track of opening brackets.
2. Iterate through the characters in the string:
   - If the character is an opening bracket (`(`, `{`, `[`), push it onto the stack.
   - If the character is a closing bracket (`)`, `}`, `]`), check if it matches the top of the stack:
     - If the stack is empty or the top of the stack does not match the current closing bracket, return false.
     - Otherwise, pop the top of the stack.
3. At the end of the iteration, the stack should be empty for the string to be valid.

💡 Explanation of Solution

- We use a stack because it follows a Last In, First Out (LIFO) structure.
- Each opening bracket is added to the stack as we encounter it.
- For each closing bracket, we check if it matches the bracket at the top of the stack:
  - If it does, the opening bracket is removed from the stack.
  - If it doesn’t, or if the stack is empty, the string is invalid.
- At the end, if the stack is not empty, there are unmatched opening brackets, so the string is invalid.

⌛ Complexity Analysis

Time Complexity: O(n)
- where n is the length of the string. Each character is processed once.

Space Complexity: O(n) 
- in the worst case, where all characters are opening brackets, requiring storage in the stack.

💻 Implementation of Solution

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char,char> brackets = {
            {'}','{'},
            {')','('},
            {']','['},
        };
 
        stack<char> open;
 
        for(const auto& c : s) {
            //current character is a closing bracket
            if(brackets.find(c) != brackets.end()) {
 
                //check if there are any opening brackets
                if(open.empty()) return false;
 
                //check if the opening bracket in the stack correspond to the closing
                if(open.top() != brackets[c]) return false;
 
                open.pop();
            }
            else {
                open.push(c);
            }
        }
        return open.empty();
    }
};

Graph View