2022/03/31

Leetcode Note: Go - Valid Parentheses

Valid Parentheses - LeetCode
https://leetcode.com/problems/valid-parentheses/

  • Go 言語で取り組んだメモ

所感

  • input された string を rune 配列にパースして、ループで対応する閉じ括弧があるかチェックすれば良さそう

実装準備

func isValid(s string) bool {
    return false
}

func main() {
    input := "()[]{}"
    fmt.Println(input)

    output := isValid(input)
    fmt.Println(output)
}

愚直に実装

func isValid(s string) bool {
    runes := []rune(s)
    
    // Parentheses counter
    // 0: '(' 
    // 1: ')'
    // 2: '{'
    // 3: '}'
    // 4: '['
    // 5: ']'
    counters := [6]int{0, 0, 0, 0, 0, 0}
    
    // loop for count
    for _, value := range runes {
        switch c := string(value); c {
            case "(":
                counters[0]++
            case ")":
                counters[1]++
            case "{":
                counters[2]++
            case "}":
                counters[3]++
            case "[":
                counters[4]++
            case "]":
                counters[5]++
        }
    }
    
    // validation Parentheses
    for i := 0; i < 3; i += 2 {
        if counters[i] != counters[i+1] {
            return false
        }
    }
    
    return true
}

=> Wrong Answer

  • Input が ([)] の場合、対応する括弧の数は OK だが組み合わせを考慮できていない
  • 括弧文字列の個数だけではなく、組み合わせも検証するロジックが必要
    • 問題文をちゃんと読もう・・・
    • しかし問題文を読んでも ([]) みたいな括弧の入れ子はどのように判定すればよいのかは読み取れず
      • まぁ Easy 問題なので、まずは入れ子のインプットは存在しないものとして考えてみる

括弧の次文字列が対応する閉じ括弧かチェックする実装

  • 愚直な if たち…

    func isValid(s string) bool {
runes := []rune(s)

for i := 0; i < len(runes); i++ {
    switch c := string(runes[i]); c {
        case "(":
            if i + 1 < len(runes) {
                if string(runes[i+1]) != ")" {
                    return false
                }
            }
        case "{":
            if i + 1 < len(runes) {
                if string(runes[i+1]) != "}" {
                    return false
                }
            }
        case "[":
            if i + 1 < len(runes) {
                if string(runes[i+1]) != "]" {
                    return false
                }
            }
    }
}

return true
}

=> Wrong Answer

  • Input が {[]} の場合が考慮できていないと
    • 結局、入れ子も考慮が必要！
  • 文字列が偶数個か判定して、偶数個の場合には前半と後半が対応しているか確認すれば良いのでは？
    • ()[]{} みたいな Input を false 判定してしまうので不完全だ
    • ただ、文字列が奇数個であれば即 false を return するのは良さそう
  • 文字列を走査して、括弧があったら、対応する閉じ括弧が他の閉じ括弧よりも先に存在するかチェックする…というアプローチで実現できそう
    • 試行錯誤してみたが結局 ()[]{} のような Input も含めて true 判定できる実装にできず

Discuss への投稿を参考に回答する

回答

Go solution beats 100% - LeetCode Discuss
https://leetcode.com/problems/valid-parentheses/discuss/1828506/Go-solution-beats-100

func isValid(s string) bool {
    stack := make([]rune, 0)
    m := map[rune]rune {
        '{': '}',
        '[': ']',
        '(': ')',
    }
    
    for _, c := range s {
        if char, ok := m[c]; ok {
            stack = append(stack, char)
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != c {
                return false
            }
            stack = stack[:len(stack)-1]
        }
        
    }
    
    return len(stack) == 0
}
  • 対応する括弧のペアを rune と rune の map で管理
    • 賢い
  • スタックを定義
    • ループ中に登場した文字が対応する括弧であればスタックに追加
    • ループ中に登場した文字が対応する括弧でなければ（閉じ括弧であれば）
      • stack[len(stack)-1] != c で、スタックに保存している最新の括弧と対応している閉じ括弧かチェックして、マッチしてなければ return false
      • true なら stack = stack[:len(stack)-1] でスタックに保存していた括弧をクリーンアップ

スタックを使うのは何となくイメージできていたが、マップを使う発想は無かった…
データ構造のボキャブラリーを増やしていきたい

See Also