2825。環状増分を使用して文字列をサブシーケンスにします

難易度： medium

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

2つの 0-Indexed strings str1およびstr2。

が与えられます。

操作では、STR1のインデックスのセットを選択し、セット内の各インデックスIについて、次の文字を循環に増分します。それは「a」は「b」になり、「b」は「c」になり、「z」は「a」になります。

return true true str2を操作を最大1回に実行することにより、str1のサブシーケンスになり、それ以外の場合は。

。

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

例1：

• 入力： str1 = "abc"、str2 = "ad"
• output： true
• 説明： STR1でインデックス2を選択します。
  increment str1 [2]は「d」になります。
  したがって、str1は「abd」になり、Str2はサブシーケンスになりました。したがって、trueは返されます。

例2：

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

例3：

• 入力： str1 = "ab"、str2 = "d"
• output： false
• 説明：この例では、sTR2を最大1回操作を使用してSTR1のサブシーケンスにすることが不可能であることを示すことができます。
  したがって、falseが返されます。

制約：

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

ヒント：

個別にインクリメントするインデックスを検討してください。
2つのポインターを維持できます。STR1のポインターIとSTR2のポインターJ、およびそれらが文字列の境界内にとどまることを保証します。
2. 。
str1 [i]とstr2 [j]の両方が一致する場合、またはstr1 [i]がstr2 [j]に一致する場合、両方のポインターを増やします。それ以外の場合は、pointer 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に実装しましょう。環状増分を使用して文字列をサブシーケンスにします

2つのポインター
1. ：iとjは、それぞれstr1とstr2の開始まで初期化されます。
一致ロジック
2. ：ループ内で、str1 [i]とstr2 [j]の文字が同じか、str2 [i]を循環的に一致させるためにstr1 [i]を増分できるかどうかを確認します。 環状増分条件は（ord（$ str1 [$ i]））1 -ord（ 'a'））％26を使用して処理されます。
   サブシーケンスチェック
：str2を完全に繰り返し（すなわち、j == m）場合、str2はstr1のサブシーケンスであることを意味します。そうでなければ、そうではありません。
3. 時間の複雑さ：

アルゴリズムはstr1を1回繰り返し、str2の各文字は一度だけチェックされるため、時間の複雑さは

o（n）

であり、nはstr1の長さです。
• スペースの複雑さ：

空間の複雑さは

o（1）

です。なぜなら、いくつかのポインターを使用しているだけで、入力サイズに応じて余分なスペースを必要としないからです。

• このソリューションでは、STR2を最大1回の循環増分操作でSTR2のサブシーケンスにすることができるかどうかを効率的にチェックします。
連絡先リンク

このシリーズが役立つと思う場合は、

リポジトリをgithubでスターにするか、お気に入りのソーシャルネットワークの投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味があります！

このようなもっと役立つコンテンツが必要な場合は、私にフォローしてください：

linkedin

• github