Valid Parentheses Problem and Solution

1. Introduction

A comprehensive guide to solving the "Valid Parentheses" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "Valid Parentheses" problem involves determining if the input string's opening and closing parentheses are valid and properly nested. This includes parentheses (), square brackets [], and curly braces {}.

2. Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets, and open brackets are closed in the correct order.

3. Solution in C++

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

bool isValid(string s) {
    unordered_map<char, char> brackets = {{')', '('}, {']', '['}, {'}', '{'}};
    stack<char> st;
    for (char c : s) {
        if (brackets.find(c) != brackets.end()) {
            if (st.empty() || st.top() != brackets[c]) return false;
            st.pop();
        } else {
            st.push(c);
        }
    }
    return st.empty();
}

// Example usage
int main() {
    string s = "{[]}";
    cout << "IsValid: " << boolalpha << isValid(s) << endl;
    return 0;
}

Output:

IsValid: true

Explanation:

1. isValid in C++ uses a stack to keep track of opening brackets.

2. It iterates through the string, pushing opening brackets onto the stack.

3. When a closing bracket is encountered, it checks if the stack's top element matches.

4. If it doesn't match or the stack is empty, the string is invalid.

5. Returns true if the stack is empty after processing all characters, indicating valid parentheses.

4. Solution in Java

import java.util.*;

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

        for (char c : s.toCharArray()) {
            if (brackets.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != brackets.get(c)) return false;
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

    // Example usage
    public static void main(String[] args) {
        String s = "{[]}";
        System.out.println("IsValid: " + isValid(s));
    }
}

Output:

IsValid: true

Explanation:

1. Java's isValid method uses a HashMap for bracket pairs and a Stack to track opens.

2. Iterates through the string, using the stack to ensure each closing bracket matches the latest opening bracket.

3. If a mismatch is found or the stack is empty when it shouldn't be, it returns false.

4. If the stack is empty at the end, the parentheses are valid.

5. Solution in Python

def is_valid(s):
    brackets = {')': '(', ']': '[', '}': '{'}
    stack = []
    for char in s:
        if char in brackets:
            top_element = stack.pop() if stack else '#'
            if brackets[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

# Example usage
s = "{[]}"
print("IsValid:", is_valid(s))

Output:

IsValid: True

Explanation:

1. is_valid in Python uses a dictionary for mapping closing to opening brackets.

2. It iterates through the string, using a list as a stack.

3. If a closing bracket is encountered, it checks if it matches the last opening bracket in the stack.

4. The string is valid if the stack is empty after processing all characters.