移动棋子以获得字符串-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。