移動棋子以獲得字串-php教程-PHP中文網

Move Pieces to Obtain a String

2337。移動棋子獲得字符串

難度：中

主題： 兩個指針，字串

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

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

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

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

true。否則，回傳 false

範例1：

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

範例2：

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

範例 3：

輸入： start = "
"
false

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

約束：

n == start.length == target.length1 5

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

提示：

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

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

解：

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

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

計劃：

長度檢查：首先，檢查兩個字串的長度是否相同。如果沒有，立即返回 false。
字元頻率檢查：起始字串中「L」、「R」和「_」的數量必須與目標字串中各自的計數相匹配，因為這些片段無法重複或銷毀，只是感動。
使用兩個指標進行棋子配對:
- 遍歷兩個字串（開始和目標）。
- 檢查開始中的每個棋子（「L」或「R」）是否可以移動到目標中對應的位置。
- 具體：
  - 「L」應該始終向左移動（即，它不能處於目標中的棋子應該向右移動的位置）。
  - 「R」應始終向右移動（即，它不能位於目標中的棋子應向左移動的位置）。

演算法說明：

過濾左右位置：
- 將字串start和target中的所有_去掉，比較L和R的序列。如果序列不同，立即傳回false。
雙指針遍歷：
- 使用兩個指標迭代start和target中的字元。
- 確保：
  - 對於L，start中的棋子只能向左移動，所以它在start中的位置應該大於或等於它在target中的位置。
  - 對於 R，start 中的棋子只能向右移動，因此它在 start 中的位置應該小於或等於它在 target 中的位置。
輸出結果：
- 遍歷時如果所有條件都滿足，則傳回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
?>

登入後複製

解釋：

初始檢查：首先，我們檢查兩個字串的長度，並確保兩個字串中「L」和「R」的計數相同。如果不是，則傳回 false。
雙指標邏輯：我們使用兩個指標i和j來遍歷兩個字串：
- 跳過空格（'_'），因為它們不會影響棋子的移動。
- 如果 start 和 target 中 i 和 j 處的字元不同，則傳回 false（因為我們無法將棋子移到不同的字元）。
- 如果在start 中找到「L」且其位置大於其目標位置，或者如果在start 中找到「R」且其位置小於其目標位置，則傳回false（因為'L ' 只能向左移動， 'R' 只能向右移動）。
邊緣情況：解決方案處理所有可能的邊緣情況，例如：
- 開始和目標中「L」或「R」的計數不同。
- 由於限製而無法移動棋子。

時間複雜度：

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

空間複雜度：

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

複雜度分析：

時間複雜度：
- 過濾底線需要O(n).
- 兩指針遍歷需要O(n).
- 整體：O(n)。
空間複雜度：
- 建立兩個字串（$startNoUnderscore 和 $targetNoUnderscore），每個字串的大小 O(n).
- 整體：O(n)。

測試用例說明：

輸入： _L__R__R_，L______RR
- L 和 R 匹配的順序。
- 每個棋子都可以依照規則移動到所需的位置。
- 輸出： true。
輸入： R_L_, __LR
- L 和 R 匹配的順序。
- R棋子不能向左移動；因此，轉換是不可能的。
- 輸出： false。
輸入： _R, R_
- R棋子不能向左移動；因此，轉換是不可能的。
- 輸出： false。