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

class Solution {
    public boolean isValid(String s) {
        
    }
}

Problem Clarification

Idea - 1

A close must always be preceded by an open of the right kind. If we use a stack, and on seeing a close if we pop the right kind of open from the stack, then in the end either there will be only opens left or the stack would be empty - later would be the valid case. The algorithm has time and space .

class Solution {
    
    private static final String closes = ")}]";
    
    public boolean isValid(String s) {
        int n = s.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = s.charAt(i);
            
            if(closes.indexOf(c) >= 0)
            {
                if(stack.isEmpty() || !match(c, stack.removeLast()))
                {
                    return false;
                }
            }
            else
            {
                stack.addLast(c);
            }
        }
        
        return stack.isEmpty();
    }
    
    private boolean match(char close, char open)
    {
        if(closes.indexOf(open) >= 0)
        {
            return false;
        }
        
        return (close==')' && open=='(')
            || (close=='}' && open=='{')
            || (close==']' && open=='[');
    }
}


Runtime: 1 ms, faster than 99.54% of Java online submissions for Valid Parentheses.
Memory Usage: 35.6 MB, less than 36.87% of Java online submissions for Valid Parentheses.