括弧の文字列が有効かどうかを確認する-PHPチュートリアル-php.cn

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

DDD

リリース： 2025-01-12 22:04:47

オリジナル

520 人が閲覧しました

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] を変更することはできません。

例 2:

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

例 3:

入力: s = ")"、ロック = "0"
出力: false
説明: がロックされているため、s[0] を変更できます。

制約:

ヒント:

解決策:

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

重要なポイント:

文字列の長さが奇数の場合、有効な括弧文字列は偶数の長さでなければならないため、すぐに false を返すことができます (それぞれの開始 (終了が必要))。
文字列を反復処理するときに、開き括弧 (() と閉じ括弧 ()) の数を追跡する必要があります。いずれかの時点で、閉じ括弧の数が開き括弧の数を超えると、文字列のバランスを取ることが不可能となり、false が返されます。
ロックされている位置 (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)
?>

ログイン後にコピー

説明：

最初のパス (左から右):
- 文字列を反復処理し、開き括弧のバランスを追跡します。開き括弧 ( ) に遭遇するたびに、開いたカウンタをインクリメントします。閉じ括弧の場合は、開いたカウンタをデクリメントします。
- 現在の文字がロック解除されている場合 (locked[i] == '0')、括弧のバランスをとる必要がある場合は、( であると想定できます。
- いずれかの時点で開いたカウンタが負になった場合、それは開き括弧よりも閉じ括弧の方が多いことを意味し、false を返します。
2 番目のパス (右から左):
- 文字列の末尾にある可能性のある開き括弧が一致しないシナリオを処理するために、同様の操作を逆に実行します。
- ここでは、閉じ括弧 ()) を閉じカウンターで追跡し、不均衡な括弧が存在しないことを確認します。
エッジケース: 文字列の長さが奇数の場合、有効な括弧文字列を形成できないため、すぐに false を返します。