1. Valid Parentheses

Description

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.

Approach 1

TC: O(n) SC: O(n)

class Solution {
    public boolean isValid(String s) {
        Stack<Character> check = new Stack<>();
        HashMap<Character,Character> brackets = new HashMap<>();
 
        brackets.put(')','(');
        brackets.put('}','{');
        brackets.put(']','[');
 
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(brackets.containsKey(c)) {
                if(!check.isEmpty() && brackets.get(c).equals(check.peek())) {
                    check.pop();
                } else {
                    return false;
                }
            } else {
                check.push(c);
            }
        }
        return check.isEmpty();
    }
}

Approach 2

• Time: O(n) Space: O(n)

class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0)
            return false;
 
        Stack<Character> brackets = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (brackets.isEmpty() && (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']'))
                return false;
            else if (s.charAt(i) == ')' && brackets.peek() == '(')
                brackets.pop();
            else if (s.charAt(i) == '}' && brackets.peek() == '{')
                brackets.pop();
            else if (s.charAt(i) == ']' && brackets.peek() == '[')
                brackets.pop();
            else
                brackets.add(s.charAt(i));
        }
 
        return brackets.isEmpty();
    }
}