有効な括弧

Easy (易)カテゴリ: stack

問題

文字列 s が与えられたとき、括弧が有効かどうかを判定する関数を作成してください。有効な括弧とは、開き括弧が同じ種類の閉じ括弧で正しく閉じられ、開き括弧が正しい順序で閉じられることを意味します。例えば、s が括弧のみで構成され、'(', ')', '{', '}', '[', ']' のみを含むとします。

例

例 2:

入力:

s = "()"

出力:

true

例 3:

入力:

s = "()[]{}"

出力:

true

例 4:

入力:

s = "(]"

出力:

false

例 5:

入力:

s = "([)]"

出力:

false

例 6:

入力:

s = "{[]}"

出力:

true

制約

1 <= s.length <= 10^4
s は '(', ')', '{', '}', '[', ']' のみで構成されています

解法

アプローチ

この問題は、括弧の有効性を判定する問題です。スタックを使用することで効率的に解くことができます。【視覚的な例】文字列: "({[]})" の処理過程： 1. '(' を読み込み、スタックに追加: スタック = ['('] 2. '{' を読み込み、スタックに追加: スタック = ['(', '{'] 3. '[' を読み込み、スタックに追加: スタック = ['(', '{', '['] 4. ']' を読み込み、スタックから '[' を取り出して対応を確認: スタック = ['(', '{'] 5. '}' を読み込み、スタックから '{' を取り出して対応を確認: スタック = ['('] 6. ')' を読み込み、スタックから '(' を取り出して対応を確認: スタック = [] 7. スタックが空になったので、括弧は有効【解法の流れ】 1. 空のスタックを用意します 2. 文字列を左から右へ操作します 3. 開き括弧（'(', '{', '['）に遭遇したら、スタックに追加します 4. 閉じ括弧（')', '}', ']'）に遭遇したら、スタックから最後の要素を取り出し、対応する開き括弧かどうかを確認します - 対応していれば、次の文字へ進みます - 対応していなければ、無効な括弧として false を返します 5. 文字列の操作が終了した後、スタックが空であれば有効な括弧、そうでなければ無効な括弧ですこの方法では、O(n)の時間複雑度で問題を解くことができます。

計算量

時間計算量

O(n) - 文字列を一度だけ操作するため

空間計算量

O(n) - 最悪の場合、すべての文字がスタックに追加される可能性があるため

実装

java

python

javaの実装

/**
 * 有効な括弧（Valid Parentheses）問題の解法
 * 
 * 【問題】
 * 文字列 s が与えられたとき、括弧が有効かどうかを判定する。
 * 有効な括弧とは、開き括弧が同じ種類の閉じ括弧で正しく閉じられ、
 * 開き括弧が正しい順序で閉じられることを意味する。
 * 
 * 【アプローチ】
 * スタックを使用します。
 * 1. 開き括弧に遭遇したら、スタックに追加
 * 2. 閉じ括弧に遭遇したら、スタックから最後の要素を取り出し、対応する開き括弧かどうかを確認
 * 3. 文字列の操作が終了した後、スタックが空であれば有効な括弧
 * 
 * 【計算量】
 * - 時間計算量: O(n) - 文字列を一度だけ操作
 * - 空間計算量: O(n) - 最悪の場合、すべての文字がスタックに追加される可能性がある
 * 
 * 【ポイント】
 * 1. スタックは「後入れ先出し」（LIFO）の特性を持ち、括弧の対応関係を確認するのに適している
 * 2. 閉じ括弧が来たとき、直前の開き括弧と対応しているかを確認することがポイント
 * 3. 最終的にスタックが空かどうかのチェックを忘れないこと
 */
import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        // 括弧を格納するスタック
        Stack<Character> stack = new Stack<>();
        
        // 文字列を左から右へ操作
        for (char c : s.toCharArray()) {
            // 開き括弧の場合、スタックに追加
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } 
            // 閉じ括弧の場合
            else {
                // スタックが空の場合、対応する開き括弧がないので無効
                if (stack.isEmpty()) {
                    return false;
                }
                
                // スタックから最後の要素を取り出す
                char top = stack.pop();
                
                // 対応する開き括弧かどうかを確認
                if ((c == ')' && top != '(') || 
                    (c == '}' && top != '{') || 
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        
        // 文字列の操作が終了した後、スタックが空であれば有効な括弧
        return stack.isEmpty();
    }
}

Java

解説

このJavaの実装では、スタックを使用して括弧の有効性を判定しています。

【具体例で解説】文字列 "({[]})" の場合：

1. '(' を読み込み、スタックに追加: stack = ['('] 2. '{' を読み込み、スタックに追加: stack = ['(', '{'] 3. '[' を読み込み、スタックに追加: stack = ['(', '{', '['] 4. ']' を読み込み、スタックから最後の要素 '[' を取り出して対応を確認: stack = ['(', '{'] 5. '}' を読み込み、スタックから最後の要素 '{' を取り出して対応を確認: stack = ['('] 6. ')' を読み込み、スタックから最後の要素 '(' を取り出して対応を確認: stack = [] 7. スタックが空になったので、true を返す

文字列 "([)]" の場合：

1. '(' を読み込み、スタックに追加: stack = ['('] 2. '[' を読み込み、スタックに追加: stack = ['(', '['] 3. ')' を読み込み、スタックから最後の要素 '[' を取り出して対応を確認 - ')' は '[' と対応していないので、false を返す

この方法の優れている点は、スタックの「後入れ先出し」の特性を活用して、最も内側の括弧から順に対応関係を確認できることです。これにより、ネストされた括弧の有効性も正確に判定できます。

追加のメモ

この問題は、スタックの基本的な使い方を理解するための良い例です。【スタックの特性】スタックは「後入れ先出し」（LIFO: Last-In-First-Out）の特性を持つデータ構造です。この特性は、括弧の対応関係を確認するのに非常に適しています。なぜなら、最も内側の括弧から順に閉じられていくからです。【異なる解法の比較】 1. カウンターを使用する方法（単純な括弧の場合） - 開き括弧と閉じ括弧の数をカウント - 時間計算量: O(n) - 空間計算量: O(1) - 問題点: 複数の種類の括弧や順序が重要な場合に対応できない 2. スタックを使用する方法（上記の解法） - 開き括弧をスタックに追加し、閉じ括弧と対応を確認 - 時間計算量: O(n) - 空間計算量: O(n) - 利点: 複数の種類の括弧や順序が重要な場合にも対応可能 3. 文字列置換法 - 有効な括弧のペア（例: "()"）を空文字列に置換し、最終的に空文字列になるかを確認 - 時間計算量: O(n²) - 空間計算量: O(n) - 問題点: 効率が悪く、大きな入力に対して遅い【実装のバリエーション】 1. 基本的なスタック実装 - 開き括弧をスタックに追加し、閉じ括弧と対応を確認 2. マッピングを使用した実装 - 閉じ括弧と開き括弧の対応関係を辞書やマップで定義 - コードがよりシンプルで読みやすくなる 3. 早期リターンの最適化 - 無効な状態を早期に検出して、処理を終了 - 例: 閉じ括弧が多すぎる場合や、文字列の長さが奇数の場合【関連する問題】 - 「最長の有効な括弧」（Longest Valid Parentheses） - 「括弧の生成」（Generate Parentheses） - 「括弧の削除」（Remove Invalid Parentheses）この問題は、スタックを使った他の問題を解く際の基礎となる重要な問題です。

問題一覧に戻る