Stack

Valid Parentheses problem

Rajeev SinghAlgorithms1 mins read

Valid Parentheses problem

Valid Parentheses problem statement

Given a string 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.

Note that an empty string is also considered valid.

Valid Parentheses solution in Java

The problem can be solved by using a stack. We iterate over the characters of the string, and for every iteration:

  • if the current character is an opening bracket, we push it in the stack.
  • if the character is a closing bracket, we pop the stack and check if the top of the stack contains its corresponding opening bracket or not.

Here is the complete solution:

import java.util.Map;
import java.util.HashMap;
import java.util.Stack;

class ValidParentheses {
  public static boolean isValid(String str) {    
    Map<Character, Character> parenthesesMapping = new HashMap<>();
    parenthesesMapping.put('(', ')');
    parenthesesMapping.put('{', '}');
    parenthesesMapping.put('[', ']');

    Stack<Character> parentheses = new Stack<>();
    for(int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if(parenthesesMapping.containsKey(c)) {
            parentheses.push(c);    
        } else {
            if(parentheses.isEmpty()) {
                return false;
            }
            char target = parentheses.pop();
            if(!parenthesesMapping.containsKey(target) || parenthesesMapping.get(target) != c) {
                return false;
            }
        }
    }
    if(!parentheses.isEmpty()) {
        return false;
    }
    return true;
  }

  public static void main(String[] args) {
    System.out.println(isValid("([)]"));
  }
}
# Output
$ javac ValidParentheses.java
$ java ValidParentheses
false