Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

 

 

Solution:

Creating a map for three kinds of parentheses.

Creating a stack.

Traversing the input string:

if the character is the left side of parentheses, add it into the stack.

if the stack is empty and the character is the right side of parentheses, return false.

if the stack is not empty but the top of the stack is not equal to that value of the map, return false.

at the end, if the stack is not empty, return false.

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> mappings = new HashMap<>();
        mappings.put(')', '(');
        mappings.put(']', '[');
        mappings.put('}', '{');

        Stack<Character> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (mappings.containsValue(c)) {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else if (stack.pop() != mappings.get(c)) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}

Time complexity: O(n)

Space complexity: O(n)