20 Valid Parentheses

Given a string containing just the characters'(',')','{','}','['and']', determine if the input string is valid.

The brackets must close in the correct order,"()"and"()[]{}"are all valid but"(]"and"([)]"are not.

Solution)

Create a map for all matching parentheses.

By using stack, if the current character is open, push to stack, otherwise, check it with the current stack.

If the stack is empty, it should be false.

class Solution {
    public boolean isValid(String s) {
      if (s == null) return true;
      // map for parenthesis matching
      Map<Character, Character> map = new HashMap<>();
      map.put('(',')');
      map.put('{','}');
      map.put('[',']');
      Stack<Character> stack = new Stack<>();
      for (char c : s.toCharArray()) {
        if (map.containsKey(c)) stack.push(c);
        else {
          if (stack.isEmpty()) return false;
          if (map.get(stack.pop()) != c) return false;
        }
      }
      return stack.isEmpty();
    }
}

Without using an extra HashMap, we can just use matching character itself.

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (c == '(') stack.push(')');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }
}