20. Valid Parentheses

📝 Problem Details

• Title: 20. Valid Parentheses
• Link: https://leetcode.com/problems/valid-parentheses/
• Difficulty: Easy
• Tags/Categories: Hashmap Strings Stack

💭What Were My Initial Thoughts?

- the order of the parentheses matter
- a stack which only contains the opening parentheses will allow us to keep track of the process of opening and closing brackets
- use a hashmap to create a key value pair relationship between opening and closing brackets of the same kind

🤔What Did I Struggle With?

~ did good on this question
- made a small blunder with the complexity analysis, saying that the space complexity was only O(log n) since we were only storing the opening brackets

💡 Explanation of Solution

- predefine a hashmap of characters where the key is the closing bracket and the value is the opening bracket
- initialize a stack for the open brackets

- iterate through the input string
- check if the char exists in the hashmap (checking if its an closing bracket)
	- if it does, check if the top of the stack is the mapped closing brakcet
	- return false if it doesnt, if it does pop the item from the stack and continue
- if it doesnt, its an opening bracket so push it into the stack

⌛ Complexity Analysis

Time Complexity: O(n) for every character in the input string s
Space Complexity: O(n) in the case where all opening brackets are stored in the stack 

💻 Implementation of Solution

class Solution {
public:
    bool isValid(string s) {
        stack<char> open;
        
        unordered_map<char, char> brackets = {
            {')','('},
            {'}','{'},
            {']','['}
        };
 
        for(const auto& c : s) {
            if(brackets.find(c) != brackets.end()) {
                if(open.empty()) return false;
                
                if(open.top() != brackets[c]) return false;
                
                open.pop();
            } else  {
                open.push(c);
            }
        }
        return open.empty();
    }
};