Valid Parentheses

Leetcode Problem: Valid Parentheses

Objective:

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.

---

Pattern: Stack

---

Approach:

1. Use a hashmap to store the paired brackets: key = closed bracket and value = open bracket.
2. If the hash map does not contain current character then it is an open bracket. Use a stack to store the open brackets.
3. Check if the stack is empty this prevents closing brackets to be added first, in this case it is not valid.
4. Check the top of the stack by popping it and if top character is not matched with closing bracket in hashmap then return false.
5. If stack is empty then return true because it is a valid parentheses.
6. If stack is not empty then return false.

---

Big-O Notation:

Time Complexity: O(n)
We have iterate n times for each character in the string.

Space Complexity: O(n)
We use a hash map data structures for storage.

---

Code:

class Solution {

    public boolean isValid(String s) {
        // use stack to store opening brackets
        Stack <Character> stack = new Stack<>();

        // use a hashmap to store pairs 
        Map <Character, Character> hashMap = new HashMap<>();
        hashMap.put(')','(');
        hashMap.put('}','{');
        hashMap.put(']','[');

        // iterate through s
        // add open brackets to the stack
        // if stack is empty or top char is not a match to c 
        // return false 

        for(char c : s.toCharArray()){
            if(!hashMap.containsKey(c)){
                stack.push(c);
            } else if(stack.isEmpty() || stack.pop() != hashMap.get(c)){
                   return false;
                }
            }
        return stack.isEmpty();        
    }
}