Valid Parentheses Problem - Java Solution

1. Introduction

In this blog post, we'll explore a common problem in string processing and stack usage - the "Valid Parentheses" problem. This problem is a typical example in coding interviews to assess understanding of basic data structures in Java.

Problem

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

1. Open brackets are closed by the same type of brackets.

2. Open brackets are closed in the correct order.

Note: An empty string is also considered valid.

2. Solution Steps

1. Initialize a stack to keep track of opening brackets.

2. Iterate through each character in the string.

3. If an opening bracket is encountered, push it onto the stack.

4. If a closing bracket is encountered, check if it matches the top element of the stack.

5. If it matches, pop the top element from the stack; otherwise, return false.

6. After the iteration, if the stack is empty, return true; otherwise, return false.

3. Code Program

import java.util.Stack;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        String input1 = "({[]})";
        String input2 = "([)]";
        System.out.println("Input: " + input1 + " - Valid: " + isValid(input1));
        System.out.println("Input: " + input2 + " - Valid: " + isValid(input2));
    }

    // Method to check if the string has valid parentheses
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>(); // Stack to keep track of opening brackets

        for (char c : s.toCharArray()) {
            // Push corresponding opening bracket onto stack if closing bracket is found
            if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else if (c == '(' || c == '{' || c == '[') {
                stack.push(c); // Push opening bracket onto stack
            } else {
                return false; // Invalid case
            }
        }

        return stack.isEmpty(); // Return true if stack is empty, false otherwise
    }
}

Output:

Input: ({[]}) - Valid: true
Input: ([)] - Valid: false

Explanation:

The input "({[]})" is valid as each type of opening bracket is matched and closed by the same type of closing bracket in the correct order. 

The method isValid uses a stack to keep track of the opening brackets. When a closing bracket is encountered, it checks whether it matches the last opened bracket. 

Conversely, the input "([)]" is invalid as the brackets are not closed in the correct order, demonstrated by the round bracket closing before the square bracket.