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

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 は英小文字のみで構成されます。

ヒント:

1. インクリメントするインデックスを個別に検討してください。
2. 2 つのポインター (str1 のポインター i と str2 のポインター j) を、文字列の範囲内に確実に保持しながら維持できます。
3. str1[i] と str2[j] の両方が一致する場合、または str1[i] のインクリメントが str2[j] と一致する場合、両方のポインターを増加します。それ以外の場合は、ポインター i のみをインクリメントします。
4. 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
?>

説明：

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

時間計算量:

• アルゴリズムは str1 を 1 回反復し、str2 の各文字は 1 回だけチェックされるため、時間計算量は O(n) になります。ここで、n は str1 の長さです。

空間の複雑さ:

• 少数のポインターのみを使用し、入力サイズに応じて追加のスペースを必要としないため、スペースの複雑さは O(1) です。

このソリューションは、最大 1 回の循環インクリメント操作で str2 を str1 のサブシーケンスにできるかどうかを効率的にチェックします。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が循環インクリメントを使用して文字列をサブシーケンスにするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。