Medium

题目描述

给你两个长度为 n 的字符串 start 和 target，两个字符串都只包含字符 ‘L’、‘R’ 和 ‘_’，其中：

  • 字符 ‘L’ 和 ‘R’ 表示片段，其中片段 ‘L’ 只有在其左边有空白空间时才能向左移动，片段 ‘R’ 只有在其右边有空白空间时才能向右移动。
  • 字符 ‘_’ 表示空白空间，可以被任意 ‘L’ 或 ‘R’ 片段占据。

如果在移动字符串 start 中的片段任意次之后可以得到字符串 target，返回 true；否则，返回 false。

示例 1：

输入：start = "_L__R__R_", target = "L______RR"
输出：true
解释：我们可以通过以下移动从 start 得到 target：
- 将第一个片段向左移动一步，start 变为 "L___R__R_"。
- 将最后一个片段向右移动一步，start 变为 "L___R___R"。
- 将第二个片段向右移动三步，start 变为 "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^5
  • start 和 target 由字符 ‘L’、‘R’ 和 ‘_’ 组成

解题思路

解题思路

这道题的核心在于理解片段移动的限制条件：

  • ‘L’ 片段只能向左移动（需要左边有空位）
  • ‘R’ 片段只能向右移动（需要右边有空位）
  • 片段不能互相跨越

分析移动规律

首先观察到一个重要性质：移动过程中片段的相对顺序不会改变。因为 ‘L’ 只能左移，‘R’ 只能右移，它们不能互相跨越。

基于这个观察，我们可以得出解决方案：

  1. 先检查两个字符串中非空白字符的序列是否相同
  2. 然后检查每个片段是否能够移动到目标位置

具体实现

使用双指针方法：

  1. 分别遍历 start 和 target，跳过空白字符 ‘_’
  2. 对于每一对对应的片段，检查：
    • 字符是否相同
    • ‘L’ 片段在 start 中的位置是否大于等于在 target 中的位置（因为只能左移）
    • ‘R’ 片段在 start 中的位置是否小于等于在 target 中的位置（因为只能右移）

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.length();
        int i = 0, j = 0;
        
        while (i < n || j < n) {
            // 跳过 start 中的空白字符
            while (i < n && start[i] == '_') i++;
            // 跳过 target 中的空白字符
            while (j < n && target[j] == '_') j++;
            
            // 如果一个字符串结束了，另一个也必须结束
            if (i == n || j == n) {
                return i == n && j == n;
            }
            
            // 字符必须相同
            if (start[i] != target[j]) {
                return false;
            }
            
            // 检查移动约束
            if ((start[i] == 'L' && i < j) || (start[i] == 'R' && i > j)) {
                return false;
            }
            
            i++;
            j++;
        }
        
        return true;
    }
};

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)
        i = j = 0
        
        while i < n or j < n:
            # 跳过 start 中的空白字符
            while i < n and start[i] == '_':
                i += 1
            # 跳过 target 中的空白字符
            while j < n and target[j] == '_':
                j += 1
            
            # 如果一个字符串结束了，另一个也必须结束
            if i == n or j == n:
                return i == n and j == n
            
            # 字符必须相同
            if start[i] != target[j]:
                return False
            
            # 检查移动约束
            if (start[i] == 'L' and i < j) or (start[i] == 'R' and i > j):
                return False
            
            i += 1
            j += 1
        
        return True

public class Solution {
    public bool CanChange(string start, string target) {
        int n = start.Length;
        int i = 0, j = 0;
        
        while (i < n || j < n) {
            // 跳过 start 中的空白字符
            while (i < n && start[i] == '_') i++;
            // 跳过 target 中的空白字符
            while (j < n && target[j] == '_') j++;
            
            // 如果一个字符串结束了，另一个也必须结束
            if (i == n || j == n) {
                return i == n && j == n;
            }
            
            // 字符必须相同
            if (start[i] != target[j]) {
                return false;
            }
            
            // 检查移动约束
            if ((start[i] == 'L' && i < j) || (start[i] == 'R' && i > j)) {
                return false;
            }
            
            i++;
            j++;
        }
        
        return true;
    }
}

var canChange = function(start, target) {
    const n = start.length;
    let i = 0, j = 0;
    
    while (i < n || j < n) {
        // 跳过 start 中的空白字符
        while (i < n && start[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历两个字符串一次，其中 n 是字符串长度
空间复杂度O(1)只使用了常数额外空间

相关题目