移動棋子以獲得字串

2337。移動棋子獲得字符串

難度：中

主題： 兩個指針，字串

給定兩個字串 start 和 target，長度皆為 n。每個字串僅包含字元“L”、“R”和“_”，其中：

• 字符'L'和'R'代表棋子，其中棋子'L'只有在其左側直接有空白空間時才能移動到左側，只有當有空白空間直接移動到右時，棋子'R'才能移動到
右
• 沒錯。 字元「_」代表一個空格，可以被
任意

個「L」或「R」棋子佔據。

如果可以透過移動字串 start 的各個部分來取得字串目標，則傳回

true。否則，回傳 false

.

範例1：

• 輸入：開始=“LR
R
• ”，目標=“L______RR”
輸出：
• true
  說明：
  • 我們可以透過執行以下操作從頭開始取得字串目標： 將第一塊往左移一步，start 變成等於「L__R
  R
  • 」。 將最後一塊往右移一步，start 變成等於「L_
  R
  • _R」。
  • 將第二支棋子向右移動三步，start 變成等於「L______RR」。
  由於可以從頭開始取得字串目標，因此我們傳回 true。

範例2：

輸入：
• start = "R_L_", target = "__LR"
輸出：
• false 說明：字串開頭的‘R’部分可以往右移一步，得到「R
  L
  • 」。
  此後，所有棋子都無法移動，因此無法從頭開始取得字串目標。

範例 3：

• 輸入： start = "
R", target = "R
• "
輸出：
• false
輸出：

字串start中的棋子只能向右移動，因此無法從start開始取得字串目標

約束：

• n == start.length == target.length 1 5

開始和目標由字元“L”、“R”和“_”組成。

提示：

2. 經過一連串的移動後，棋子的順序可以改變嗎？

嘗試將 s 中的每個片段與 e 中的片段進行配對。

解：

我們需要檢查是否可以透過按照給定規則移動棋子（「L」和「R」）將字串開頭轉換為字串目標。需要考慮的主要限制是：

• ‘L’只能向左移動（不能與其他‘L’或‘R’棋子交叉）。
• 'R'只能向右移動（不能越過其他'L'或'R'棋子）。
• 我們可以使用任何空格（'_'）來移動棋子。

計劃：

1. 長度檢查：首先，檢查兩個字串的長度是否相同。如果沒有，立即返回 false。

2. 字元頻率檢查：起始字串中「L」、「R」和「_」的數量必須與目標字串中各自的計數相匹配，因為這些片段無法重複或銷毀，只是感動。

3. 使用兩個指標進行棋子配對:

   • 遍歷兩個字串（開始和目標）。
   • 檢查開始中的每個棋子（「L」或「R」）是否可以移動到目標中對應的位置。
   • 具體：
     • 「L」應該始終向左移動（即，它不能處於目標中的棋子應該向右移動的位置）。
     • 「R」應始終向右移動（即，它不能位於目標中的棋子應向左移動的位置）。

演算法說明：

1. 過濾左右位置：

   • 將字串start和target中的所有_去掉，比較L和R的序列。如果序列不同，立即傳回false。

2. 雙指針遍歷：

   • 使用兩個指標迭代start和target中的字元。
   • 確保：
     • 對於L，start中的棋子只能向左移動，所以它在start中的位置應該大於或等於它在target中的位置。
     • 對於 R，start 中的棋子只能向右移動，因此它在 start 中的位置應該小於或等於它在 target 中的位置。

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. 雙指標邏輯：我們使用兩個指標i和j來遍歷兩個字串：

   • 跳過空格（'_'），因為它們不會影響棋子的移動。
   • 如果 start 和 target 中 i 和 j 處的字元不同，則傳回 false（因為我們無法將棋子移到不同的字元）。
   • 如果在start 中找到「L」且其位置大於其目標位置，或者如果在start 中找到「R」且其位置小於其目標位置，則傳回false（因為'L ' 只能向左移動， 'R' 只能向右移動）。

3. 邊緣情況：解決方案處理所有可能的邊緣情況，例如：

   • 開始和目標中「L」或「R」的計數不同。
   • 由於限製而無法移動棋子。

時間複雜度：

• 時間複雜度為 O(n)，其中 n 是輸入字串的長度。這是因為我們只遍歷每個字串一次。

空間複雜度：

• 空間複雜度為 O(1)，因為我們只使用固定數量的額外空間。

複雜度分析：

1. 時間複雜度：

   • 過濾底線需要O(n).
   • 兩指針遍歷需要O(n).
   • 整體：O(n)。

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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是移動棋子以獲得字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！