スタックで括弧の対応を判定する

スタック問題 23

3 種類のかっこだけでできた文字列を見て、開きと閉じの対応が正しいかを返します。開いたかっこを積んでおき、閉じるたびに一番上と照らす、スタックの練習です。

海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)

問題

( ) [ ] { } の 6 つの文字だけでできた文字列 s を受け取ります。開きかっこと閉じかっこの対応が正しければ true、正しくなければ false を返す関数を書いてください。

対応が正しいとは、どの閉じかっこも、同じ種類で、まだ閉じていない一番新しい開きかっこを閉じていることです
最後には、開いたままのかっこが残っていてはいけません
空の文字列は、対応が正しいものとして true を返します
s の長さは 0 以上 10000 以下です

入力と出力の例

例 1

入れ子になっていても、内側から順に閉じていれば正しい対応です。

s = "{[()]}()"

true

例 2

数はそろっていても、閉じる順が違えば正しくありません。

s = "([)]"

false

例 3

開いたままのかっこが残っています。

s = "[{}"

false

面接での聞かれ方

面接では、短い一文で渡されることが多いです。

「かっこだけの文字列があります。正しく閉じているか判定してください」
最初は () の 1 種類だけで出され、解けたら「では 3 種類なら？」と広げられることがあります
「空の文字列はどう扱いますか？」と、端の場合を聞かれることもあります

かっこ以外の文字が来るのか、空の文字列をどうするのかを、書く前に確かめておくと迷いません。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「スタックとキュー」に、この型の要点を表とコードでまとめています。

スタックは後から入れた物を先に、キューは先に入れた物を先に取り出します。括弧の対応や、順番待ちの処理の形です。

まず考える手順

段 1

まずは 1 種類だけの場合を考えます。開きで 1 足し、閉じで 1 引く数を 1 つ持てば済みます。途中で数が負になるか、最後に 0 でなければ正しくありません。

段 2

3 種類になると、数だけでは足りません。例 2 の ([)] は、どの種類も開きと閉じの数がそろっているのに、正しくありません。閉じかっこが来たとき、「いま閉じてよいのはどの種類か」を知る必要があります。

段 3

閉じてよいのは、まだ閉じていない一番新しい開きかっこです。最後に入れた物を最初に取り出すので、スタックがちょうど合います。開きかっこはスタックに積み、閉じかっこが来たら一番上を取り出して、種類が合うかを照らします。

段 4

正しくない場合を、取りこぼさないように並べます。閉じかっこが来たのにスタックが空のとき、取り出した開きかっこと種類が違うとき、最後までなめてもスタックに残りがあるときの 3 つです。どれか 1 つでも起きれば false です。

解答

Python

def valid_brackets(s):
    pairs = {
        ")": "(",
        "]": "[",
        "}": "{",
    }
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack:
                return False
            top = stack.pop()
            if top != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

JavaScript

function validBrackets(s) {
  const pairs = {
    ")": "(",
    "]": "[",
    "}": "{",
  };
  const stack = [];
  for (const ch of s) {
    if (ch in pairs) {
      if (stack.length === 0) {
        return false;
      }
      const top = stack.pop();
      if (top !== pairs[ch]) {
        return false;
      }
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

Go

func validBrackets(
	s string,
) bool {
	pairs := map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
	}
	stack := []rune{}
	for _, ch := range s {
		open, ok := pairs[ch]
		if !ok {
			stack = append(stack, ch)
			continue
		}
		n := len(stack)
		if n == 0 {
			return false
		}
		top := stack[n-1]
		stack = stack[:n-1]
		if top != open {
			return false
		}
	}
	return len(stack) == 0
}

辞書は「閉じかっこから、対になる開きかっこ」を引けるように作っています。閉じかっこが来たときに、取り出した開きかっこと 1 回で照らせるからです。

計算量

時間は O(n) です。文字列を前から 1 回なめ、積むのも取り出すのも一定の手間です
使う記憶は O(n) です。開きかっこだけが続くと、全部をスタックに積みます
段 1 の数を数える書き方は記憶が O(1) ですが、3 種類のかっこには使えません

よくある間違い

種類ごとに数を数えるだけで済ませる。例 2 の ([)] を正しいと答えてしまいます。順を見るにはスタックが要ります
空のスタックから取り出す。 ")" のように閉じかっこから始まる文字列で、Python は例外で止まります。JavaScript は undefined が返り、気づきにくい間違いになります。Go は stack[n-1] が範囲の外になり、panic で止まります。取り出す前に空かどうかを調べます
最後の残りを調べ忘れる。例 3 の [{} は、途中では一度も食い違いません。最後にスタックが空かどうかで決まります

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.2確認日 2026年10月24日

def valid_brackets(s: str) -> bool: """ Goal: 何を返すか idea1: まず思いつく案 -> runtime: O(?) space: O(?) idea2: もっと速い案 -> runtime: O(?) space: O(?) edge case: 空、1 つだけ、など """ # ここに書きます pass # 「実行」を押すと、この行の結果が出ます print(valid_brackets("{[()]}()"))