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.
3. Every close bracket has a corresponding open bracket of the same type.

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

1. Use a Stack: We'll utilize a stack data structure to keep track of opening brackets.
2. Iterate through the String: Traverse the input string s character by character.
3. Opening Bracket: If we encounter an opening bracket ('(', '[', or '{'), push it onto the stack.
4. Closing Bracket: If we encounter a closing bracket (')', ']', or '}'), check the following:
   • If the stack is empty, it means there's no matching opening bracket, so the string is invalid.
   • If the stack is not empty, pop the top element from the stack. This represents the corresponding opening bracket.
   • Check if the popped opening bracket and the current closing bracket match. If they don't match, the string is invalid.
5. After Iteration: After iterating through the entire string, if the stack is empty, it means all opening brackets have been correctly closed, and the string is valid. Otherwise, there are unmatched opening brackets, and the string is invalid.

Explanation

The stack acts as a memory to store opening brackets. When we encounter a closing bracket, we check the top of the stack to see if it's the matching opening bracket. This ensures that brackets are closed in the correct order. If the stack is empty at the end, it implies all opening brackets have been successfully paired with closing brackets.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public bool IsValid(string s) {
        Stack<char> stack = new Stack<char>();
        Dictionary<char, char> bracketMap = new Dictionary<char, char>() {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        foreach (char c in s) {
            if (bracketMap.ContainsValue(c)) { //Opening bracket
                stack.Push(c);
            } else if (bracketMap.ContainsKey(c)) { //Closing bracket
                if (stack.Count == 0 || stack.Pop() != bracketMap[c]) {
                    return false; //Stack empty or mismatch
                }
            }
        }

        return stack.Count == 0; //True if stack is empty (all brackets matched)
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n) in the worst case. The stack could potentially hold up to n/2 elements if all brackets are opening brackets. In the average case, the space complexity is much lower.