LeetCodeに毎日挑戦してみた 20. Valid Parentheses（Python、Go）

はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

Go言語入門＋アルゴリズム脳の強化のためにGolangとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

6問目（問題20)

20. Valid Parentheses

• 問題内容(日本語訳)

文字列を考えるsだけで文字を含む'('、')'、'{'、'}'、'['と']'、入力文字列が有効であるかどうかを決定。

入力文字列は、次の場合に有効です。

1. 開いたブラケットは、同じタイプのブラケットで閉じる必要があります。
2. 開いたブラケットは正しい順序で閉じる必要があります。

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

考え方

1. stack配列と辞書(map)を用意する。
2. mapには対応する記号を入力
3. 文字列を一文字ずつ見ていき、括弧の始まりならstackに追加し、閉じ括弧ならstackの直近のものを取り出して合っているかどうか確認。

説明

1. stackとdict(map)を定義する。
2. dict = {"]":"[", "}":"{", ")":"("}
3. for文で文字を一文字ずつみていきます。

• 解答コード

class Solution:
    def isValid(self, s):
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return stack == []

​ if char in dict.values():　で括弧始まりかどうか

​ elif char in dict.keys(): 　で括弧終わりかどうか

​ popで最新のstackの文字を取得

​ appendでstackに代入です。

• Goでも書いてみます！

  func isValid(s string) bool {
    stack := make([]rune, 0)
    m := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    for _, c := range s {
        switch c {
        case '(', '{', '[':
            stack = append(stack, c)
        case ')', '}', ']':
            if len(stack) == 0 || stack[len(stack)-1] != m[c] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
  }

こちらのコードは少し難しいですが、Goで文字列を一文字ずつ見るためにこのコードになりました。

​ for _, c := range s のループ処理では文字列stringsを一文字ずつ読み取ります。その時cはrune型になるのでmapやスタックもrune型で定義しました。

せっかくGolang書いてるからswitich文で処理を書きました。

• 自分メモ(Go)

文字列を一文字ずつ見るとrune

スライスにappend(固定長でないのでok)