Valid Parentheses easy

Problem Statement

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([)]" Output: false

Example 5:

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

Steps and Explanation

This problem can be efficiently solved using a stack data structure. The algorithm works as follows:

1. Initialization: Create an empty stack.
2. Iteration: Iterate through the input string s character by character.
3. Opening Bracket: If the current character is an opening bracket ('(', '[', or '{'), push it onto the stack.
4. Closing Bracket: If the current character is a closing bracket (')', ']', or '}'), check the following:
   • If the stack is empty, the string is invalid (no matching opening bracket).
   • If the stack is not empty, pop the top element from the stack. This represents the expected matching opening bracket.
   • Compare the popped element with the current closing bracket. If they don't form a valid pair, the string is invalid.
5. Post-Iteration: After iterating through the entire string, if the stack is empty, it means all opening brackets have been matched with their corresponding closing brackets, and the string is valid. Otherwise, the string is invalid.

Code (Java)

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false; // Unmatched closing bracket
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                    return false; // Mismatched brackets
                }
            }
        }
        return stack.isEmpty(); // True if all opening brackets are matched
    }
}

Complexity Analysis

• Time Complexity: O(N), where N is the length of the input string. We iterate through the string once.
• Space Complexity: O(N) in the worst case. The stack can grow up to the size of the input string if the string contains only opening brackets. In the best case (e.g., an empty string or a string with perfectly matched brackets), the space complexity is O(1).