Example: Valid Parentheses - rFronteddu/general_wiki GitHub Wiki

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.

o determine if a string containing just the characters '(', ')', '{', '}', '[' and ']' is valid, we can use a stack to keep track of the opening brackets. The string is valid if every opening bracket has a corresponding closing bracket in the correct order.

Approach:

• Initialize a Stack: Use a stack to keep track of the opening brackets.
• Traverse the String: For each character in the string:
  • If it is an opening bracket ('(', '{', '['), push it onto the stack.
  • If it is a closing bracket (')', '}', ']'), check if the stack is not empty and if the top of the stack is the matching opening bracket. If it matches, pop the stack; otherwise, the string is invalid.
• Final Check: After processing all characters, the stack should be empty if the string is valid.

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;
                }
                char top = stack.pop();
                if (c == ')' && top != '(' || 
                    c == ']' && top != '[' || 
                    c == '}' && top != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}