LeetCode 题解工作台
移动片段得到字符串
给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L' 、 'R' 和 '_' 组成，其中： 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
替换操作实际上是将 `L` 往左移动（`L` 左边为 `_` 时才能移动），`R` 往右移动（`R` 右边是 `_` 时才能移动），但 `L` 无法穿过 `R`。所以，如果去掉 `start` 和 `target` 中的所有 `_`，剩下的字符应该是相同的，否则返回 `false`。 我们使用双指针 和 从头到尾遍历 `start` 和 `target`：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
- 字符
'L'和'R'表示片段，其中片段'L'只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段'R'只有在其右侧直接存在一个 空位 时才能向 右 移动。 - 字符
'_'表示可以被 任意'L'或'R'片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
示例 1：
输入：start = "_L__R__R_", target = "L______RR" 输出：true 解释：可以从字符串 start 获得 target ，需要进行下面的移动： - 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。 - 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。 - 将第二个片段向右移动三步，字符串现在变为 "L______RR" 。 可以从字符串 start 得到 target ，所以返回 true 。
示例 2：
输入：start = "R_L_", target = "__LR" 输出：false 解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。 但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
示例 3：
输入：start = "_R", target = "R_" 输出：false 解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。
提示：
n == start.length == target.length1 <= n <= 105start和target由字符'L'、'R'和'_'组成
解题思路
方法一：双指针
替换操作实际上是将 L 往左移动（L 左边为 _ 时才能移动），R 往右移动（R 右边是 _ 时才能移动），但 L 无法穿过 R。所以，如果去掉 start 和 target 中的所有 _，剩下的字符应该是相同的，否则返回 false。
我们使用双指针 和 从头到尾遍历 start 和 target：
- 如果当前字符为
L且 ，那么这个L无法向右移动，返回false； - 如果当前字符为
R且 ，那么这个R无法向左移动，返回false。
如果双指针均遍历到末尾，返回 true。
时间复杂度 ，其中 表示字符串 start 或 target 的长度。
相似题目：
class Solution:
def canChange(self, start: str, target: str) -> bool:
a = [(v, i) for i, v in enumerate(start) if v != '_']
b = [(v, i) for i, v in enumerate(target) if v != '_']
if len(a) != len(b):
return False
for (c, i), (d, j) in zip(a, b):
if c != d:
return False
if c == 'L' and i < j:
return False
if c == 'R' and i > j:
return False
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each string is scanned once. Space complexity is O(1) as only two pointers are used, with no extra arrays or data structures. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
They may ask about moving 'L' pieces left versus 'R' pieces right.
- question_mark
They may hint at scanning both strings simultaneously to maintain order invariants.
- question_mark
They may test edge cases with consecutive underscores or overlapping movement.
常见陷阱
外企场景- error
Ignoring the direction constraints of 'L' and 'R' pieces and assuming free movement.
- error
Failing to skip underscores correctly when aligning pointers in both strings.
- error
Not checking that extra unmatched pieces remain at the end after scanning.
进阶变体
外企场景- arrow_right_alt
Allow diagonal or bidirectional movement and see how constraints change.
- arrow_right_alt
Check transformations with multiple identical pieces in sequence to test order preservation.
- arrow_right_alt
Consider using a queue to simulate piece movements instead of two pointers.