駒を動かして文字列を取得する

2337。駒を動かして文字列を取得します

難易度: 中

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

2 つの文字列 start と target が与えられ、どちらも長さは n です。各文字列は文字「L」、「R」、「_」のみで構成されます。

• 文字「L」と「R」は駒を表します。駒「L」は、すぐ左に空白スペースがある場合にのみ左に移動できます。そして、ピース「R」は、直接空白スペースがある場合にのみ、右に移動できます。そうです。
• 文字「_」は、「L」または「R」部分のいずれかが占有することができる空白スペースを表します。

文字列の開始部分を何回でも移動することで文字列ターゲットを取得できる場合は、true を返します。それ以外の場合は false.

を返します。

例 1:

• 入力: 開始 = "LRR"、ターゲット = "L______RR"
• 出力: true
• 説明: 次の手順を実行することで、最初から文字列ターゲットを取得できます。
  • 最初のピースを左に 1 ステップ移動すると、start は "L__RR" と等しくなります。
  • 最後のピースを右に 1 ステップ移動すると、開始値が "L_R_R" になります。
  • 2 番目のピースを右に 3 ステップ移動すると、開始値は "L______RR" になります。
  • 最初から文字列ターゲットを取得できるのでtrueを返します。

例 2:

• 入力: 開始 = "R_L_"、ターゲット = "__LR"
• 出力: false
• 説明: 文字列開始部分の「R」部分を右に 1 ステップ移動して、「RL」を取得できます。
  • その後、どの駒も移動できなくなるため、最初から文字列ターゲットを取得することは不可能です。

例 3:

• 入力: 開始 = "R"、ターゲット = "R"
• 出力: false
• 出力: 文字列の先頭の部分は右にのみ移動できるため、先頭から文字列ターゲットを取得することは不可能です。

制約:

• n == start.length == target.length
• 1 5
• start と target は文字「L」、「R」、「_」で構成されます。

ヒント:

1. 一連の動きの後、駒の順序が変わることがありますか?
2. s の各部分を e の部分と一致させてみてください。

解決策:

指定されたルールに従って部分 ('L' と 'R') を移動することによって、文字列開始を文字列ターゲットに変換できるかどうかを確認する必要があります。考慮すべき主な制約は次のとおりです:

• 「L」は左にのみ移動できます (他の「L」または「R」ピースを横切ることはできません)。
• 「R」は右にのみ移動できます (他の「L」または「R」ピースを横切ることはできません)。
• 任意の空白スペース ('_') を使用してピースを移動できます。

プラン：

1. 長さのチェック: まず、両方の文字列の長さが同じかどうかを確認します。そうでない場合は、すぐに false を返します。

2. 文字頻度チェック: 開始文字列の「L」、「R」、および「_」の数は、ターゲット文字列のそれぞれの数と一致する必要があります。これは、部分を複製したり破棄したりできないためです。 、移動のみです。

3. 2 つのポインターを使用したピースのマッチング:

   • 両方の文字列 (開始文字列とターゲット文字列) をトラバースします。
   • スタートの各ピース (「L」または「R」) がターゲットの対応する位置に移動できるかどうかを確認します。
   • 具体的には:
     • 「L」は常に左に移動する必要があります (つまり、ターゲット内のピースが右に移動する位置にあってはなりません)。
     • 「R」は常に右に移動する必要があります (つまり、ターゲット内のピースが左に移動する位置にあってはなりません)。

アルゴリズムの説明:

1. L および R 位置のフィルター:

   • 文字列 start と target の両方からすべての _ を削除して、L と R のシーケンスを比較します。シーケンスが異なる場合は、すぐに false を返します。

2. 2 点トラバーサル:

   • 2 つのポインターを使用して、開始文字とターゲット文字を反復処理します。
   • 次のことを確認してください:
     • L の場合、スタートのピースは 左 にしか移動できないため、スタートの位置はターゲットの位置以上である必要があります。
     • R の場合、スタートのピースは 右 にしか移動できないため、スタートの位置はターゲットの位置以下である必要があります。

3. 出力結果:

   • トラバース中にすべての条件が満たされた場合、true を返します。それ以外の場合は false を返します。

このソリューションを PHP で実装してみましょう: 2337。駒を動かして文字列を取得します

<?php
/**
 * @param String $start
 * @param String $target
 * @return Boolean
 */
function canChange($start, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
var_dump(canChange("_L__R__R_", "L______RR")); // true
var_dump(canChange("R_L_", "__LR"));          // false
var_dump(canChange("_R", "R_"));              // false
?>

説明：

1. 初期チェック: まず、両方の文字列の長さをチェックし、両方の文字列の「L」と「R」の数が同じであることを確認します。そうでない場合は、false を返します。

2. 2 つのポインター ロジック: 2 つのポインター i と j を使用して、両方の文字列を走査します。

   • 空白スペース ('_') はピースの移動に影響を与えないため、読み飛ばしてください。
   • start と target の i と j の文字が異なる場合は、false を返します (ピースを別の文字に移動できないため)。
   • start で「L」が見つかり、ターゲット位置よりも大きい位置にある場合、または「R」が start で見つかり、ターゲット位置よりも小さい位置にある場合は、false を返します ('L であるため) ' は左にのみ移動でき、'R' は右にのみ移動できます)。

3. エッジ ケース: このソリューションは、次のような考えられるすべてのエッジ ケースを処理します。

   • スタートとターゲットの「L」または「R」のカウントが異なります。
   • 制約により駒を移動できません。

時間計算量:

• 時間計算量は O(n) です。ここで、n は入力文字列の長さです。これは、各文字列を 1 回だけトラバースするためです。

空間の複雑さ:

• 固定量の追加スペースのみを使用しているため、スペースの複雑さは O(1) です。

複雑さの分析:

1. 時間計算量:

   • アンダースコアのフィルタリングには O(n) がかかります。
   • 2 点トラバーサルには O(n) がかかります。
   • 全体: O(n).

2. 空間の複雑さ:

   • 2 つの文字列 ($startNoUnderscore と $targetNoUnderscore) が作成され、それぞれのサイズは O(n) です。
   • 全体: O(n).

テストケースの説明:

1. 入力: _L__R__R_、L______RR

   • L と R のシーケンスが一致します。
   • 各ピースはルールに従って必要な位置に移動できます。
   • 出力: true。

2. 入力: R_L_、__LR

   • L と R のシーケンスが一致します。
   • R ピースは左に移動できません。したがって、変換は不可能です。
   • 出力: false。

3. 入力: _R、R_

   • R ピースは左に移動できません。したがって、変換は不可能です。
   • 出力: false。

この実装は効率的であり、問​​題の制約に準拠しているため、大きな入力サイズに適しています。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が駒を動かして文字列を取得するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。