循環インクリメントを使用して文字列をサブシーケンスにする-PHPチュートリアル-php.cn

循環インクリメントを使用して文字列をサブシーケンスにする

Barbara Streisand

リリース： 2024-12-08 13:29:10

オリジナル

430 人が閲覧しました

Make String a Subsequence Using Cyclic Increments

2825。循環インクリメントを使用して文字列をサブシーケンスにする

難易度: 中

トピック: 2 つのポインター、文字列

2 つの 0 インデックス付き 文字列 str1 と str2 が与えられます。

操作では、str1 のインデックスの セット を選択し、セット内のインデックス i ごとに、str1[i] を次の文字まで周期的にインクリメントします。つまり、「a」は「b」になり、「b」は「c」になり、同様に「z」は「a」になります。

操作 最大 1 回を実行することで str2 を str1 のサブシーケンスにできる場合は true を返し、それ以外の場合は falseを返します。

注: 文字列のサブシーケンスは、残りの文字の相対的な位置を乱すことなく、文字の一部 (おそらく何も削除しない) を削除することによって、元の文字列から形成される新しい文字列です。

例 1:

入力: str1 = "abc"、str2 = "ad"
出力: true
説明: str1 のインデックス 2 を選択します。
- str1[2] をインクリメントして 'd' にします。
- したがって、str1 は "abd" になり、str2 はサブシーケンスになります。したがって、true が返されます。

例 2:

入力: str1 = "zc"、str2 = "ad"
出力: true
説明: str1 のインデックス 0 と 1 を選択します。
- str1[0] をインクリメントして 'a' にします。
- str1[1] をインクリメントして「d」になります。
- したがって、str1 は「ad」になり、str2 はサブシーケンスになります。したがって、true が返されます。

例 3:

入力: str1 = "ab"、str2 = "d"
出力: false
説明: この例では、この操作を 1 回だけ使用して str2 を str1 のサブシーケンスにすることは不可能であることがわかります。
- したがって、 false が返されます。

制約:

1 5
1 5
str1 と str2 は英小文字のみで構成されます。

ヒント:

インクリメントするインデックスを個別に検討してください。
2 つのポインター (str1 のポインター i と str2 のポインター j) を、文字列の範囲内に確実に保持しながら維持できます。
str1[i] と str2[j] の両方が一致する場合、または str1[i] のインクリメントが str2[j] と一致する場合、両方のポインターを増加します。それ以外の場合は、ポインター i のみをインクリメントします。
j が str2 の末尾にある場合、一致するものが見つからなくなった後、str2 を str1 のサブシーケンスにすることができます。

解決策:

str1 の任意の文字に対して最大 1 つの循環インクリメント操作を実行することで、str2 を str1 のサブシーケンスにできるかどうかを確認する必要があります。

説明：

2 つのポインターを使用します。i は str1 で、j は str2 です。
str1[i] の文字が str2[j] と一致する場合、両方のポインターを前方に移動します。
str1[i] を str2[j] と一致するように (周期的に) インクリメントできる場合は、それらを一致させてから両方のポインターを移動しようとします。
上記の条件がどちらも当てはまらない場合は、str1 のポインタ i のみを移動します。
最後に、str2 のすべての文字を一致させることができれば、str2 を str1 のサブシーケンスにすることができますが、それ以外の場合はできません。

このソリューションを PHP で実装してみましょう: 2825。循環インクリメントを使用して文字列をサブシーケンスにする

<?php
/**
 * @param String $str1
 * @param String $str2
 * @return Boolean
 */
function canMakeSubsequence($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$str1 = "abc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "zc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "ab";
$str2 = "d";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: false
?>

ログイン後にコピー

説明：

2 つのポインター: i と j は、それぞれ str1 と str2 の先頭に初期化されます。
マッチングロジック: ループ内で、str1[i] と str2[j] の文字が同じかどうか、または str2[j] と一致するように str1[i] を周期的にインクリメントできるかどうかをチェックします。
- 循環インクリメント条件は、(ord($str1[$i]) 1 - ord('a')) % 26 を使用して処理され、str1[i] が str2[j] と一致するようにインクリメントできるかどうかをチェックします。
サブシーケンスチェック: str2 を完全に反復処理した場合 (つまり、j == m)、str2 が str1 のサブシーケンスであることを意味します。それ以外の場合は、そうではありません。