NUHMAN.com

Introduction

LeetCode 20: Valid Parentheses is a classic data structure problem that tests your understanding of stacks and character matching.

Given a string containing only brackets, determine if the input string is valid — that is:

• Every open bracket has a corresponding close bracket.
• Brackets are closed in the correct order.

In this article, we’ll solve this problem using a stack-based approach in Go (Golang).

Problem Statement

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

A string is valid if:

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

Examples

go

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

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

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

Approach: Stack

1. Use a stack to keep track of open brackets.
2. For each character:

• If it's an opening bracket, push it onto the stack.
• If it's a closing bracket, check the top of the stack:
• If the stack is empty or the top doesn't match the closing bracket, return false.
• Otherwise, pop the top.

1. If the stack is empty after processing, the string is valid.

Go Implementation

go

package main

import (
    "fmt"
)

func isValid(s string) bool {
    stack := []rune{}
    bracketMap := map[rune]rune{
        ')': '(', 
        '}': '{', 
        ']': '[',
    }

    for _, ch := range s {
        switch ch {
        case '(', '{', '[':
            stack = append(stack, ch)
        case ')', '}', ']':
            if len(stack) == 0 || stack[len(stack)-1] != bracketMap[ch] {
                return false
            }
            stack = stack[:len(stack)-1] // Pop
        }
    }

    return len(stack) == 0
}

func main() {
    testCases := []string{
        "()",
        "()[]{}",
        "(]",
        "([)]",
        "{[]}",
        "",
    }

    for _, test := range testCases {
        fmt.Printf("Input: %q → Is Valid? %v\n", test, isValid(test))
    }
}

Step-by-Step Example: "{[]}"

Stack flow:

• { → push → ["{"]
• [ → push → ["{", "["]
• ] → top is [ → pop → ["{"]
• } → top is { → pop → []

Stack is empty at the end → Valid ✅

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string (each character is processed once).
• Space Complexity: O(n), in the worst case all characters are opening brackets.

Key Takeaways

• A stack is ideal for solving problems involving reversals, matching pairs, and nested structures.
• Using a map makes it easy to look up matching pairs.
• Always check for stack underflow (i.e., popping from an empty stack).