アルゴリズム概要

💡 この問題を一言で言うと：「開き括弧と閉じ括弧の対応関係と順序が正しいかどうかを判定する問題」です。

'('、')'、'{'、'}'、'['、']' だけからなる文字列 s が与えられます。すべての開き括弧が正しい種類・正しい順序で閉じられているなら true、そうでなければ false を返します。

⚠️ なぜ単純な方法では解けないのか

  • 括弧の「数」を数えるだけでは不十分です。開き括弧の数と閉じ括弧の数が一致していても、閉じる順序が壊れている入力（例："([)]"）を見逃してしまいます。
  • 閉じ括弧が来たときに「一番最近開かれた、まだ閉じられていない括弧」と比較する必要があり、これには「後入れ先出し」の性質を持つデータ構造（スタック）が必要です。
O(n)
時間計算量
O(n)
空間計算量
Stack
採用アプローチ
4言語共通
アルゴリズムの統一度

📥 入出力例

s = "()[]{}"
出力: true
3種類の括弧がそれぞれ正しい順序で閉じられているため
s = "([)]"
出力: false
'(' が閉じられる前に '[' が ')' によって閉じられようとしているため

ステップバイステップ解説

ここでは特定の言語に依存せず、「文字列を読みながらスタックを操作する」という処理の流れを、 代表例 s = "([)]" を使って1ステップずつ確認します。 この考え方は、後の「コード（4言語）」セクションでPython / TypeScript / Go / Rustのどの実装にも共通する土台になります。

実装（Python / TypeScript / Go / Rust）

4言語とも「開き括弧が来たら対応する閉じ括弧をスタックに積み、閉じ括弧が来たらスタック最上部と直接比較する」という同じアルゴリズムを採用しています。 タブを切り替えて、それぞれの言語らしい書き方・エラーの扱い方の違いを見比べてみましょう。

計算量分析

📖 Big-O 記法の読み方

O(1)
入力サイズに関わらず
常に一定の速さ
O(n)
入力が2倍になると
処理も約2倍
O(n log n)
入力が2倍になると
処理は約2倍強
O(n²)
入力が2倍になると
処理は約4倍
言語 採用アルゴリズム 時間計算量 空間計算量 実装上の特徴
Python スタック法 O(n) O(n) list をスタックに、dict で対応表引き
TypeScript スタック法 O(n) O(n) string[] をスタックに、readonly な対応表
Go スタック法 O(n) O(n) []byte をプリアロケーション、switch で分岐
Rust スタック法 O(n) O(n) Vec<char> を事前確保、Option<char> で安全に比較

🔍 なぜこの計算量になるのか

文字列 s の各文字を1回ずつしか読まないため、時間計算量は文字列長 n に比例する O(n) になります。 これより速くすることは、各文字を最低1回は確認する必要がある以上、理論上不可能です。 空間計算量については、最悪ケース（全て開き括弧、例："((((("）ではスタックに全文字が積まれるため O(n) になります。 括弧の出現数だけを数えるO(1)空間のアプローチも存在しますが、順序の検証ができず不正解になるため採用していません。

言語間比較

同じアルゴリズムでも、言語ごとに「メモリの扱い方」や「エラーの表現方法」が異なります。 ここでは4言語の実装を横並びで比較し、それぞれの言語特有の設計判断を振り返ります。

観点 Python TypeScript Go Rust
採用アルゴリズム スタック法 スタック法 スタック法 スタック法
スタックの実体 list[str] string[] []byte Vec<char>
メモリ確保の特徴 動的拡張（償却O(1)） 動的拡張（V8内部最適化） makeでプリアロケーションし再アロケーション回避 with_capacityで事前確保し再アロケーション回避
エラー表現の方法 例外（Exception） undefinedの型レベル表現 パニックを避ける範囲チェック Option<T>による安全な比較
メモリ管理方式 GC（参照カウント+世代別GC） GC（V8のGC） GC（並行GC） 所有権システム（GC無し）
型安全性の担保方法 pylance静的解析+実行時isinstance コンパイル時の構造的型付け+型ガード 静的型付け+go vet コンパイル時の所有権チェック

相違点の背景

Python・TypeScript・GoはいずれもGC（ガベージコレクション、＝使い終わったメモリを自動で回収する仕組み）を持つ言語であり、 メモリの解放タイミングを意識する必要がありません。一方Rustは所有権システム（＝コンパイル時にメモリの管理者を1つに定める仕組み） でGC無しにメモリ安全性を実現しており、これがエラー表現の違いに最も強く表れています。 Python/TypeScript/Goが「例外」または「安全な値（undefinedやパニック回避チェック）」でエラーを扱うのに対し、 RustのOption<T>は「値があるかないか」を型として持つため、 呼び出し側は必ずどちらのケースかを意識させられます。 本問題はデータ構造・計算量の面で言語ごとの有利不利が生じるタイプの問題ではないため、4言語とも同じスタック法を採用していますが、 対応表の型・エラーの扱い方には各言語のイディオム（＝その言語で自然とされる書き方）がそれぞれ表れています。

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください（五十音順）。

▶ イミュータブル
一度作られたら中身を変更できない性質のこと。PythonのstrやTypeScript/JavaScriptの文字列はこの性質を持ちます。
▶ ガベージコレクション（GC）
使い終わったメモリを自動で回収する仕組み。Python・TypeScript（JavaScript）・Goが持つ機能で、プログラマがメモリ解放のタイミングを意識しなくてよくなります。Rustはこの仕組みを持たず、代わりに所有権システムでメモリを管理します。
▶ 型ガード（TypeScript）
typeofやin演算子などで実行時に値の型を確認し、その情報をもとにTypeScriptの型を絞り込む仕組みです。JavaScriptには無い、TypeScript独自のコンパイル時チェック機能です。
▶ 借用（Rust）
所有権を渡さずに値を参照する仕組み。&T（読み取り専用）と&mut T（書き込み可能）があります。
▶ 所有権（Rust）
値を「誰が管理するか」をコンパイル時に決めるRust独自の仕組み。JavaやPythonのようなガベージコレクタなしで、メモリの安全性をコンパイル時に保証できます。
▶ スタック
後入れ先出し（LIFO）の構造を持つデータ構造。お皿の積み重ねのように、最後に積んだものを最初に取り出します。本問題では「まだ閉じられていない開き括弧（に対応する閉じ括弧）」を記録するために使います。
▶ スライス（Go）
Goで配列の一部（または全体）を扱うためのデータ構造。[]byteのように書き、動的にサイズを変えられます。
▶ 静的解析
プログラムを実行せずに、コードを読むだけでバグや型エラーを検出する手法。Pythonのpylance、TypeScriptのコンパイラ、Goのgo vet、Rustのclippyがそれぞれ担っています。
▶ 償却計算量（Amortized Complexity）
個々の操作は時々遅くなることがあっても、多数回の操作全体で平均すると一定時間で済むという計算量の考え方。Pythonのlist.appendの再確保コストはこの考え方で「ならすとO(1)」とみなされます。
▶ パニック（Go / Rust）
GoやRustで回復不能なエラーが発生した際に起きる強制終了。スライスや配列への範囲外アクセスなどで発生します。本問題のコードでは、範囲外アクセスが起きる前に必ず空チェックを行うことで回避しています。
▶ プリアロケーション（Go / Rust）
必要なメモリをあらかじめまとめて確保しておくこと。Goのmake([]byte, 0, len(s))やRustのVec::with_capacity(s.len())のように書くことで、途中の再確保を防ぎ高速化できます。
▶ Big-O記法
入力の大きさに対して、処理にかかる時間やメモリがどう増えるかを表す記法。O(n)なら「入力が2倍になると処理も約2倍になる」ことを意味します。
▶ LIFO（Last In, First Out）
「最後に入れたものを最初に出す」という、スタックの動作原則。本問題の「一番内側の括弧から閉じる」という性質とぴったり一致します。
▶ readonly（TypeScript）
配列やオブジェクトの値を変更できないようにする修飾子。JavaScriptには無い、TypeScript独自のコンパイル時チェック機能で、意図しない書き換えを防ぎます。