Javaを使用した最長バランスの括弧内のプレフィックスの長さ

この記事では、Javaを使用して最長のバランスの取れた括弧のプレフィックスの長さを求める方法を説明します。まず、いくつかの例を用いて問題を理解し、次にそれを求める2つの異なるアプローチを学習します。

問題の説明

ここでは、括弧を含む文字列が与えられ、文字列からバランスの取れた括弧の集合の長さを求める必要があります。つまり、すべての開き括弧"("に対して閉じ括弧")"があれば、それをバランスが取れていると呼びます。

プレフィックスは、文字列の先頭からのバランスの取れた集合を定義します。例えば、括弧の集合'(())()'の場合、'(())'のみを考慮します。

入力と出力のシナリオ

より良い理解のために、いくつかの入力と出力のシナリオを見てみましょう。

• 入力文字列が"(()"の場合、バランスの取れた括弧のプレフィックスは()なので、長さは2です。
• 入力文字列が"((()()))((("の場合、バランスの取れた括弧のプレフィックスは((()()))なので、長さは8です。
• 入力文字列が"(()())()()"の場合、バランスの取れた括弧のプレフィックスは(()())なので、長さは6です。

最長のバランスの取れた括弧のプレフィックスの長さは、次のようにして求めることができます。

• スタックデータ構造を使用する
• 開き括弧と閉じ括弧を数える

スタックデータ構造を使用する

スタックを使用できます。スタックから開き括弧 '(' が見つかった場合は、それをスタックにプッシュします。閉じ括弧が見つかった場合は、スタックをポップし、カウンタ変数を2増分します（バランスの取れたペアの長さは2です）。これを続け、空のスタックになった時点で、カウンタ変数を返します。

アルゴリズム

アルゴリズムは以下のとおりです。

<code><p><b>ステップ1：</b>スタックとカウンタを初期化します。</p>
<p><b>ステップ2：</b>文字列の各文字を反復処理します。</p></code>

• 文字が(の場合、スタックにプッシュします。
• 文字が)の場合、スタックをポップします。
• カウンタを2増分します。
• スタックが空かどうかを確認します。
• 空の場合、ループを終了します。

ステップ3：最後にカウンタを返します。

例

<code><p><b>ステップ1：</b>スタックとカウンタを初期化します。</p>
<p><b>ステップ2：</b>文字列の各文字を反復処理します。</p></code>

出力

入力文字列は：((())(( 最長のバランスの取れた括弧のプレフィックスの長さは：6

開き括弧と閉じ括弧を数える

このアプローチでは、countとlengthという2つの変数を使用します。文字列から文字が"("の場合、countを1増分し、文字が")"の場合、countを1減分し、lengthを2増分します。countが0かどうかを確認し、0の場合はループを終了してlengthを返します。

例

import java.util.Stack;

public class Example {
   public static int longestBalancedPrefix(String s) {
      Stack<Character> stack = new Stack<>();
      int count = 0;
      for (int i = 0; i < s.length(); i++) {
         char c = s.charAt(i);
         if (c == '(') {
            stack.push(c);
         } else if (c == ')') {
            if (!stack.isEmpty()) {
               stack.pop();
               count += 2;
            }
         }
         if (stack.isEmpty()) {
            break;
         }
      }
      return count;
   }

   public static void main(String[] args) {
      String s = "((())(((";
      int length = longestBalancedPrefix(s);
      System.out.println("入力文字列は：" + s);
      System.out.println("最長のバランスの取れた括弧のプレフィックスの長さは：" + length);
   }
}

出力

入力文字列は ((())())(()) 最長のバランスの取れた括弧のプレフィックスの長さは 8

以上がJavaを使用した最長バランスの括弧内のプレフィックスの長さの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。