King Of Interviews

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 must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

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

Try this Problem on your own or check similar problems:

Solution:

public boolean isValid(String s) {
  Stack<Character> stack = new Stack<>();
  Map<Character, Character> bracketMapping = new HashMap<>();
  bracketMapping.put(')', '(');
  bracketMapping.put('}', '{');
  bracketMapping.put(']', '[');

  for(char c: s.toCharArray()){
    if(c == '(' || c == '{' || c == '['){
      stack.push(c);
    }else if(!stack.empty() && stack.peek() == bracketMapping.get(c)){
      stack.pop();
    }else{
      return false;
    }
  }

  return stack.empty();
}

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(n)

Explanation:

Since we traverse the whole string we have linear time complexity O(n) where n is the length of the string, also in worst case scenario we would just have different kinds of open brackes and our stack helper data structure would grow to n elements in size leading to O(n) in space complexity. The solution is based on idea that every closing bracket has to have it’s pair in the string and they should also be in correct order. Stack is a good data structure for this scenario, since for each closing bracket (), }, ]) we’re only interested in the last (, { or [ bracket so we need a LIFO (last in, first out) data structure. We traverse the string and if we encounter an opening bracket we push it to the stack otherwise we have a closing bracket and we use bracketMapping to check if we have it’s pair on the top of stack. If we have it, we pop it from the stack and continue our traversal, otherwise we don’t have a matching bracket so we have to return false. Finnaly we check if the stack is empty (all brackets are paired) and we return the result of that check as our final result.

Valid Parentheses