アルゴリズム図: 括弧が有効かどうかを判断するにはどうすればよいでしょうか?

[[346613]]

この記事はWeChatの公開アカウント「Java Chinese Community」から転載したもので、著者はLei Geです。この記事を転載する場合は、Java Chinese Community 公式アカウントにお問い合わせください。

今日お話しする質問は、今年のビリビリの筆記試験で実際に出題された質問であり、スタックに関する面接の定番の質問でもあります。

これまでの記事を読んで、私が次に書く記事が「アルゴリズムの図解」に関する一連の記事であることに気づいた友人は多いと思います。途中に他の種類の記事が少し混じるかもしれませんが、今年の私の記事の焦点は「アルゴリズムとデータ構造」になります。

このアルゴリズムシリーズを書く際には、次の 2 つの点に注意します。

誰もがアルゴリズムの解決方法を理解できるように、より直感的で理解しやすい図の形でアイデアを説明します。
知識ポイントを紹介した後、学んだことを定着させるために多くの演習を行います。たとえば、「スタック」構造について説明し終わった後、「スタック」に関する一連の典型的な面接の質問を練習します。

アルゴリズムを学ぶ鍵は、問題を解決するアイデアを習得することです。アイデアが正しければ、コードを書くのは時間の問題です。

それでは、本日の公式コンテンツに入りましょう...

トピック

'('、')'、'{'、'}'、'['、']' のみで構成される文字列が与えられた場合、その文字列が有効かどうかを判断します。

有効な文字列は次の要件を満たしている必要があります。

開き括弧は、同じタイプの閉じ括弧で閉じる必要があります。
開き括弧は正しい順序で閉じる必要があります。
空の文字列は有効な文字列とみなされることに注意してください。

例1:

入力: "()"   
 
出力: true

例2:

入力: "()[]{}"   
 
出力: true

例3:

入力: "(]"  
出力: false

例4:

入力: "([)]"出力: false

例5:

入力: "{[]}"  
出力: true  
 LeetCode アドレス: https://leetcode-cn.com/problems/valid-parentheses

問題解決

この質問は、括弧の対称性を検証するものです。たとえば、「([{}])」のような文字列は正しく、true を返すはずですが、「([{})]」のような文字列は間違っており、false を返すはずです。

上記の質問からわかるように、括弧は丸括弧、角括弧、中括弧の 3 つのカテゴリに分けられます。次に、スタックの先入れ後出し機能を使用して、最初にすべての左括弧 (「(」、「[」、「{」) をスタックにプッシュし、次に右括弧に遭遇したときに、スタックの先頭の要素と一致させます。たとえば、「)」に遭遇したときに、スタックの先頭が「(」である場合、一致が成功したことを意味し、スタックの先頭の要素がポップされ、文字列ループ処理が続行されます。一致が間違っている場合は、直接 false が返されます。

文字列「(([]))」を一致させたいとします。これは合法でしょうか? 実行フローは次のようになります。

まず左括弧を見つけてスタックにプッシュします。

次に左括弧が来て、スタックにプッシュされ続けます。

次に、再び左括弧があり、これをスタックにプッシュし続けます。

次に右括弧が続きます。これはスタックの一番上の要素と一致します。"[]" は有効な括弧のペアです。一致が成功すると、スタックの一番上の要素がポップされます。

次に右括弧が続きます。これはスタックの一番上の要素と一致します。"()" は有効な括弧のペアです。一致が成功すると、スタックの一番上の要素がポップされます。

文字列ループが終了し、スタックが空になると、この文字列の括弧マッチングが正当であることが証明されます。最終的な効果は次の図に示されています。

次に、コードを使用してプロセス全体を実装してみましょう...

実装コード1

パブリックブール値isValid(文字列s) {
 int slen = s.length(); // 括弧の長さ
    if (slen % 2 == 1) { // 括弧がペアになっていない場合は、直接falseを返す 
戻る 間違い;
    }
    // 比較のための括弧をすべてマップに保存し、比較に使用します
    Map<文字,文字> map = new HashMap<>();
    map.put( ')' , '(' );
    map.put( '}' , '{' );
    map.put( ']' , '[' );
    // 括弧にアクセスするためのスタックを定義する（比較を支援するため）
    Stack<文字> stack = new Stack<>();
 for ( int i = 0; i < slen; i++) { // すべての文字をループする
char c = s.charAt(i);
        if (map.containsKey(c)) { // は右括弧（')' 、 '}'など）です。
            if (stack.isEmpty() || stack.peek() != map.get(c)) { // スタックが空か括弧が一致しない
戻る 間違い;
            }
            stack.pop(); // は括弧のペアで、スタックを実行します（左括弧と右括弧を削除します）
        } else { // 左括弧、スタックに直接プッシュ
            スタックをプッシュします。
        }
    }
 stack.isEmpty()を返します。
 }

LeetCode でコードを送信すると、実行結果は次のようになります。

コード分析

上記のコードのマップコレクションは、括弧の一致ルールを定義するために使用されます。たとえば、「)」の一致値は「(」、「]」の一致値は「[」などです。次に、検証する文字列をループし、左括弧に遭遇したときにそれを直接スタックにプッシュし、右括弧に遭遇したときにそれをスタックの一番上の要素と一致させます。文字列のループ全体が完了するまで待機します。スタックが空の場合、文字列内の括弧は有効であることを意味します。

複雑性分析

時間計算量: O(n)、文字列全体を走査します。空間計算量: O(n)。

実装コード2

スタックを使用するだけでなく、Java の replace メソッドを使用してこれを実現することもできます。文字列内の括弧をループして、「()」や「[]」や「{}」を空の括弧に置き換えることができます。最後に、実行が完了した後に文字列が空であれば、文字列内の括弧が正当であることを意味します。具体的な実装コードは次のとおりです。

パブリックブール値isValid(文字列s) {
長さ;
        する {
            len = s.length();
            // シンボルのペアを削除する
            s = s.replace ( "()" , "" ) .replace ( "[]" , "" ) .
交換する（ "{}" 、 "" ）;
        } while (len != s.length()); // これ以上の置換は行えません。replaceメソッドは文字を置換しません。
 s.length() == 0を返します。
    }

LeetCode でコードを送信すると、実行結果は次のようになります。

実行結果から判断すると、2 つの実行効率の違いは依然として明らかです。

要約する

この記事では、ビリビリからの実際のテスト問題について話しました。これはスタックに関する典型的な面接の質問でもあります。スタックの特性（先入れ後出し）を利用して、すべての左括弧をスタックにプッシュし、右括弧に遭遇したときに、スタックの一番上の要素と一致させます。文字列のループが終了し、スタックが空になると、この文字列の括弧が合法であることを意味します。もちろん、実際のインタビューでは、Java の replace メソッドをバックアップソリューションとして使用することもできます。replace メソッドの実装は比較的簡単ですが、パフォーマンスはあまり良くありません。

<<: まったく新しいスペルチェッカー、ハミング曲認識機能！ Google の「Search On」キャンペーンの最新ハイライトを 1 つの記事で読む

>>: ケンブリッジ 2020 人工知能パノラマレポート、将来予測される 8 つの AI トレンド