括弧の文字列が有効かどうかを確認する

2116年。括弧の文字列が有効かどうかを確認します

難易度: 中

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

括弧文字列は、「(」と「)」だけで構成される空ではない文字列です。次の条件のいずれかが当てはまる場合に有効です:

• ()です。
• AB (A と B を連結) として記述することができます。A と B は有効な括弧文字列です。
• これは (A) として記述できます。A は有効な括弧文字列です。

括弧文字列 s とロックされた文字列が与えられ、どちらも長さは n です。 locked は、「0」と「1」のみで構成されるバイナリ文字列です。 各 ロックされたインデックス i について、

• locked[i] が「1」の場合、s[i] を変更できません。
• しかし、locked[i] が '0' の場合は、s[i] を '(' または ')' に変更できます。

s を有効な括弧文字列

にできる場合は、true を返します。それ以外の場合は false を返します。

例 1:

• 入力: s = "))()))"、ロック = "010100"
• 出力: true
• 説明: locked[1] == '1' および locked[3] == '1' であるため、s[1] または s[3] を変更することはできません。
  s を有効にするために、s[2] と s[5] は変更しないまま、s[0] と s[4] を '(' に変更します。

例 2:

• 入力: s = "()()"、ロック = "0000"
• 出力: true
• 説明: s はすでに有効であるため、変更を加える必要はありません。

例 3:

• 入力: s = ")"、ロック = "0"
• 出力: false
• 説明: がロックされているため、s[0] を変更できます。
  s[0] を '(' または ')' に変更しても s は有効になりません。

制約:

n == s.length == locked.length
1 5 s[i] は '(' または ')' です。
locked[i] は '0' または '1' です。

ヒント:

奇数の長さの文字列は有効ですか?
左から右に、ロックされた ')' が見つかった場合は、その左側にあるロックされた '(' またはロックされていないインデックスのいずれかでバランスをとる必要があります。どちらも存在しない場合、どのような結論が導き出されますか? 両方が存在する場合、どちらを使用するのがより好ましいですか?
上記の後、'(' のインデックスがロックされ、さ​​らにロックされていないインデックスが追加された可能性があります。ロックされた '(' のバランスをとるにはどうすればよいですか? ロックされた '(' のバランスをとれない場合はどうすればよいですか?

解決策:

制約とロックされた位置の動作を念頭に置きながら、段階的にアプローチしていきます。

重要なポイント:

1. 文字列の長さが奇数の場合、有効な括弧文字列は偶数の長さでなければならないため、すぐに false を返すことができます (それぞれの開始 (終了が必要))。
2. 文字列を反復処理するときに、開き括弧 (() と閉じ括弧 ()) の数を追跡する必要があります。いずれかの時点で、閉じ括弧の数が開き括弧の数を超えると、文字列のバランスを取ることが不可能となり、false が返されます。
3. ロックされている位置 (locked[i] == '1') とロック解除されている位置 (locked[i] == '0') は慎重に扱う必要があります。ロックされていない位置ではキャラクターを変更できますが、ロックされた位置では変更できません。

アルゴリズム：

• ステップ 1: 文字列 s の長さが奇数かどうかを確認します。その場合は、すぐに false を返します。
• ステップ 2: 文字列を左から右にループして、括弧のバランスを追跡します。
  • カウンターを使用して、開き括弧 (と閉じ括弧) のバランスを追跡します。
  • いずれかの時点で、閉じ括弧の数が開き括弧を超えた場合は、ロックされた位置にバランスを取るのに十分な柔軟性があるかどうかを確認してください。
  • 文字列全体を処理した後、括弧のバランスが取れているかどうか、つまり、一致しない開き括弧が残っていないかどうかを確認します。

このソリューションを PHP で実装してみましょう: 2116。括弧文字列が有効かどうかを確認します

<?php /**
 * @param String $s
 * @param String $locked
 * @return Boolean
 */
function canBeValid($s, $locked) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s = "))()))";
$locked = "010100";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = "()()";
$locked = "0000";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = ")";
$locked = "0";
var_dump(canBeValid($s, $locked));  // Output: bool(false)
?>

説明：

1. 最初のパス (左から右):

   • 文字列を反復処理し、開き括弧のバランスを追跡します。開き括弧 ( ) に遭遇するたびに、開いたカウンタをインクリメントします。閉じ括弧の場合は、開いたカウンタをデクリメントします。
   • 現在の文字がロック解除されている場合 (locked[i] == '0')、括弧のバランスをとる必要がある場合は、( であると想定できます。
   • いずれかの時点で開いたカウンタが負になった場合、それは開き括弧よりも閉じ括弧の方が多いことを意味し、false を返します。

2. 2 番目のパス (右から左):

   • 文字列の末尾にある可能性のある開き括弧が一致しないシナリオを処理するために、同様の操作を逆に実行します。
   • ここでは、閉じ括弧 ()) を閉じカウンターで追跡し、不均衡な括弧が存在しないことを確認します。

3. エッジケース: 文字列の長さが奇数の場合、有効な括弧文字列を形成できないため、すぐに false を返します。

時間計算量:

• 両方のパス (左から右および右から左) には線形時間 O(n) がかかります。n は文字列の長さです。したがって、全体的な時間計算量は O(n) となり、入力サイズの制約に対して効率的です。

このソリューションは、指定された制約内で問題を正しく処理します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が括弧の文字列が有効かどうかを確認するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。