20. Valid Parentheses#

Code#

 1public boolean isValid(String s) {
 2  Stack<Character> stk = new Stack();
 3
 4  for (char c : s.toCharArray()) {
 5    if (c == '(' || c == '[' || c == '{') {
 6      stk.push(c);
 7    } else if (c == ')' || c == ']' || c == '}') {
 8      if (stk.isEmpty()) return false;
 9
10      char top = stk.peek();
11      if (
12        (c == ')' && top != '(') ||
13        (c == ']' && top != '[') ||
14        (c == '}' && top != '{')
15      ) {
16        return false;
17      }
18      stk.pop();
19    }
20  }
21
22  return stk.isEmpty();
23}

Time Complexity

Space Complexity

\(\mathcal{O}(n)\)

\(\mathcal{O}(n)\)