Easy

Valid Parentheses

Given a string `s` containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets, and open brackets must be closed in the correct order.

Examples

Input:s = "()[]{}"

Output:true

All brackets are properly closed.

Input:s = "(]"

Output:false

Mismatched brackets.

Constraints

1 <= s.length <= 10^4
s consists of parentheses only '()[]{}'.

Approach

Repeatedly search for and replace consecutive matching bracket pairs ("()", "[]", "{}") with empty strings. If the string eventually becomes empty, it means all brackets were matched correctly. If we can no longer find any pairs but the string is not empty, it is invalid.

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Each string replacement can take O(n) time, and we might do this O(n/2) times. This is very inefficient.

Solution.java

1class Solution {2    public boolean isValid(String s) {3        while (s.contains("()") || s.contains("[]") || s.contains("{}")) {4            s = s.replace("()", "");5            s = s.replace("[]", "");6            s = s.replace("{}", "");7        }8        return s.isEmpty();9    }10}