かっこの対応が正しいか｜コーディング面接問題

問題

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

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

入力と出力の例

例 1

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

入力

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

出力

true

例 2

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

入力

s = "([)]"

出力

false

例 3

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

入力

s = "[{}"

出力

false

面接での聞かれ方

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

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

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

まず考える手順

段 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;
}

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

計算量

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

よくある間違い

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

面接での話し方の例

書き始める前に、方針を短く口に出します。

「1 種類なら数を数えれば済みますが、3 種類あると閉じる順も見る必要があります。閉じてよいのは一番新しく開いたかっこなので、スタックに積んでおき、閉じかっこが来たら一番上と照らします。時間も記憶も O(n) です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 2 の ([)] でたどります。( と [ を積みます。次の ) で一番上を取り出すと [ なので、種類が合わず、ここで false を返します。数を数えるだけでは見落とす場合です。」

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