**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:**

- Use a hashmap to store the paired brackets: key = closed bracket and value = open bracket.
- If the hash map does not contain current character then it is an open bracket. Use a stack to store the open brackets.
- Check if the stack is empty this prevents closing brackets to be added first, in this case it is not valid.
- Check the top of the stack by popping it and if top character is not matched with closing bracket in hashmap then return false.
- If stack is empty then return true because it is a valid parentheses.
- 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();
}
}
```

## Top comments (0)