。括弧を有効にするための最小追加数

921。括弧を有効にするための最小追加数

難易度: 中

トピック: 文字列、スタック、貪欲

括弧文字列は、次の場合にのみ有効です。

• これは空の文字列です、
• AB (A と B を連結) として記述することができます (A と B は有効な文字列です)、または
• これは (A) と書くことができます。A は有効な文字列です。

括弧文字列 s が与えられます。 1 回の操作で、文字列の任意の位置に括弧を挿入できます。

• たとえば、s = "()))" の場合、開き括弧を "(()))" にするか、閉じ括弧を "())))" として挿入できます。

を有効にするために必要な最小移動数を返します。

例 1:

• 入力: s = "())"
• 出力: 1

例 2:

• 入力: s = "((("
• 出力: 3

制約:

• 1
• s[i] は '(' または ')' です。

解決策:

入力文字列を有効にするために、開き括弧または閉じ括弧をいくつ追加する必要があるかを判断する必要があります。有効な文字列とは、すべての開き括弧 '(' に対応する閉じ括弧 ')' があることを意味します。

この問題は、次のような単純な対抗アプローチを使用して解決できます。

• 変数バランスを使用して、開き括弧と閉じ括弧の間の現在のバランスを追跡します。
• 別の変数加算を使用して、必要な括弧の最小数をカウントします。

アプローチ：

1. 文字列 s の各文字をループします。
2. 文字が「(」の場合、残高を 1 増やします。
3. 文字が「)」の場合、残高を 1 減らします。
   • 残高がマイナスになる場合は、開き括弧よりも閉じ括弧の数が多いことを意味します。バランスをとるために開き括弧を追加する必要があるため、追加を 1 ずつ増やしてバランスを 0 にリセットします。
4. ループの最後で、残高が 0 より大きい場合は、一致しない左かっこがあることを示しているため、追加に残高を追加します。

このソリューションを PHP で実装してみましょう: 921。かっこを有効にするための最小追加数

<?php /**
 * @param String $s
 * @return Integer
 */
function minAddToMakeValid($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s1 = "())";
echo minAddToMakeValid($s1);  // Output: 1

$s2 = "(((";
echo minAddToMakeValid($s2);  // Output: 3
?>

説明：

• 文字列 s = "())" の場合:
  • 2 番目の ')' に遭遇すると残高がマイナスになるため、加算が増加します。
  • 最後に、残高は 0、加算は 1 であるため、文字列を有効にするためには 1 の加算が必要です。
• 文字列 s = "(((":
  • 最後に一致しない '(' が 3 つあるため、残高は 3 になります。
  • 結果は加算残高、0 3 = 3 です。

この解の時間計算量は O(n) です。n は文字列の長さとスペースです少数の変数のみを使用するため、O(1) の複雑さ。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。括弧を有効にするための最小追加数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。