20. Valid Parentheses

Problem Overview

Brackets close in the reverse order they open, so the most recent unmatched opening bracket is always the one the next closing bracket must match.

Intuition

Brackets close in the reverse order they open, so the most recent unmatched opening bracket is always the one the next closing bracket must match. A stack holds exactly those unmatched brackets. Pushing the closing character each opener expects turns every check into one comparison with the top of the stack. A string with an odd length can never balance, and once more than half the string is open brackets, the rest cannot close them all.

Algorithm

1Return false if the length is odd.
2Allocate a character stack of size n / 2.
3For an opening bracket, push the closing bracket it needs. If the stack is already full, return false.
4For a closing bracket, return false if the stack is empty or its top is a different character. Otherwise pop it.
5After the scan, the string is valid only when the stack is empty.

Example Walkthrough

Input: s = "{[]}"

1.The brace pushes a closing brace, and the square bracket pushes a closing square bracket.
2.The next character is a closing square bracket. It matches the top, so it is popped.
3.The final closing brace matches the remaining top. The stack ends empty.

Output: true

Common Pitfalls

•A closing bracket with an empty stack is invalid, as in a string that starts with ).
•Leftover openers at the end make the string invalid even if every closer matched.
•Crossed pairs such as ([)] fail because the top of the stack expects ] when ) arrives.
•Counting each bracket type separately misses crossed pairs. The order matters, so a stack is needed.

20.cs

// Approach: Each opening bracket pushes the closing bracket it expects. A
// closing bracket must equal the top of that stack. An odd length can never
// balance, and the scan stops once more brackets are open than characters
// remain to close them.
// Complexity: O(n) time, O(n) extra space.
public class Solution
{
    public bool IsValid(string s)
    {
        int n = s.Length;
        if ((n & 1) == 1)
            return false;

        char[] stack = new char[n / 2];
        int top = 0;
        for (int i = 0; i < n; i++)
        {
            char ch = s[i];
            char expect = ch switch
            {
                '(' => ')',
                '{' => '}',
                '[' => ']',
                _ => '\0',
            };

            if (expect != '\0')
            {
                if (top == stack.Length)
                    return false;
                stack[top++] = expect;
            }
            else if (top == 0 || stack[--top] != ch)
                return false;
        }

        return top == 0;
    }
}

Was this solution helpful?