移动片段得到字符串

难度: Medium

给你两个字符串 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.length
1 <= n <= 10⁵
start 和 target 由字符 'L'、'R' 和 '_' 组成

Submission

运行时间: 112 ms

内存: 17.2 MB

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        if start.count('L') != target.count('L') or start.count('R') != target.count('R'):
            return False
            
        lc, rc = 0, 0
        for s, t in zip(start, target):
            if t == 'L':
                if rc != 0: return False
                lc += 1
            if s == 'L':
                lc -= 1
                if lc < 0: return False
            if s == 'R':
                if lc != 0: return False
                rc += 1
            if t == 'R':
                rc -= 1
                if rc < 0: return False
        return True

Explain

此题解首先检查`start`和`target`字符串中'L'和'R'的数量是否相等，如果不相等，则直接返回`false`，因为无法通过移动字符来平衡数量不同的片段。接着，使用两个计数器`lc`和`rc`分别跟踪'L'和'R'的位置偏差。遍历`start`和`target`字符串的每个字符，同时比较两者的字符。如果目标位置`t`需要一个'L'，则增加`lc`；如果起始位置`s`有一个额外的'L'，则减少`lc`。如果`lc`变为负数，表示在`target`中，'L'的位置在`start`之前，这是不可能的，因为'L'只能向左移动。类似的逻辑应用于'R'字符，但是注意`rc`的处理方式与`lc`相反，因为'R'只能向右移动。如果在任何时刻，`lc`和`rc`计数器的状态违反了移动规则，就返回`false`。如果整个过程中没有违规，最后返回`true`。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        # 检查'L'和'R'的数量是否匹配
        if start.count('L') != target.count('L') or start.count('R') != target.count('R'):
            return False
            
        lc, rc = 0, 0 # 初始化'L'和'R'的计数器
        # 遍历start和target的每个字符
        for s, t in zip(start, target):
            if t == 'L':
                # 目标位置需要'L'
                if rc != 0: return False # 如果有未匹配的'R'，则无法放置'L'
                lc += 1
            if s == 'L':
                # 起始位置有额外的'L'
                lc -= 1
                if lc < 0: return False # 多余的'L'不能被移动到需要的位置
            if s == 'R':
                # 起始位置有'R'
                if lc != 0: return False # 不能移动'R'，如果有未匹配的'L'
                rc += 1
            if t == 'R':
                # 目标位置需要'R'
                rc -= 1
                if rc < 0: return False # 多余的'R'不能被移动到需要的位置
        return True

Explore

在遍历字符串的过程中，如果在`target`中的位置`t`需要一个'L'而在`start`中的相应位置`s`不是'L'，此时只增加`lc`计数器而不立即返回`false`是因为我们正在统计`target`中需要移动到的'L'字符数量。只有当`lc`计数器变为负数时，即出现在`start`中没有足够的'L'字符可以移动到`target`相应位置时，才返回`false`。这种延迟判断的方式允许我们在整个字符串遍历结束前，保留对字符位置匹配的灵活处理。

在处理'R'字符的过程中，遇到起始位置有额外的'R'时需要检查`lc`是否为0，是因为`lc`计数器代表`L`字符的位置偏差。如果`lc`不为0，意味着在当前`R`字符的位置之前，存在未匹配或未正确放置的`L`字符，由于`L`只能向左移动，如果此时移动`R`字符（只能向右移动），可能会导致`L`和`R`的路径冲突或位置错误。因此，只有当所有`L`字符都已正确处理（即`lc`为0），才能安全地处理`R`字符。

在此算法中，`lc`和`rc`计数器分别跟踪`L`和`R`字符在`start`和`target`中的位置偏差。如果在任意时刻`lc`或`rc`变为负数，这表示在`target`字符串中，`L`或`R`字符出现的位置在`start`中没有足够的字符可以对应移动过去，即`target`要求的位置无法通过合法的移动得到。例如，`lc`变负意味着`target`中需要的`L`字符在`start`中没有足够的对应字符可以左移满足位置要求，因此违反了题目的移动规则，需要返回`false`。