[LeetCode/Go] 20.Valid Parentheses

概要

↓の解法メモです。
https://leetcode.com/problems/valid-parentheses/description/

問題概要

三種類の括弧（()[]{}）からなる文字列が渡されるので、それらが正しい形式で記述されているかを判別します。正しいかの基準は以下の通り。

1. 開き括弧は、同じタイプの閉じ括弧でとじられなければいけない
2. 開き括弧は、正しい順序でとじなければいけない
3. すべての閉じ括弧に、同じタイプの対応する開き括弧がなければいけない

例えば ([]) は OK ですが、([)] はダメです。

スタックを利用する

開き括弧をスタックに突っ込み、閉じ括弧が来たらスタックの頭に入っている要素とタイプを比較、同じタイプなら OK としてチェックしています。

• 筆者のコード

var (
    openChars  = []rune{ '(', '[', '{' }
    closeChars = []rune{ ')', ']', '}' }
    pairMap    = map[rune]rune{ '(':')', '[':']', '{':'}' }
)
func isValid(s string) bool {
    stack := []rune{}
    for _, c := range s {
        if slices.Contains(openChars, c) {
            stack = append(stack, c)
        }
        if slices.Contains(closeChars, c) {
            if len(stack) != 0 && c == pairMap[stack[len(stack)-1]] {
                stack = stack[:len(stack)-1]
            } else {
                return false
            }
        }
    }
    if len(stack) != 0 {
        return false
    }
    return true
}

• 最適なコード（Solution から引用）

↑のコードの一部の条件式を反転させ、3行くらい節約してる。かしこい。
https://leetcode.com/problems/valid-parentheses/solutions/6126238/simpill-super-easy-beginners

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

    for _, char := range s {
        if char == '(' || char == '{' || char == '[' {
            stack = append(stack, char) // Push opening brackets
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[char] {
                return false // Mismatch or empty stack
            }
            stack = stack[:len(stack)-1] // Pop matching bracket
        }
    }

    return len(stack) == 0
}