Medium

题目描述

在一个由 ‘L’、‘R’ 和 ‘X’ 字符组成的字符串中，如 “RXXLRXRXL”，一次移动包括用 “LX” 替换一个 “XL”，或者用 “XR” 替换一个 “RX”。给定起始字符串 start 和结束字符串 result，当且仅当存在一系列移动可以将 start 转换为 result 时，返回 True。

示例 1：

输入：start = "RXXLRXRXL", result = "XRLXXRRLX"
输出：true
解释：我们可以通过以下步骤将 start 转换为 result：
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

示例 2：

输入：start = "X", result = "L"
输出：false

约束条件：

  • 1 <= start.length <= 10^4
  • start.length == result.length
  • start 和 result 只包含字符 ‘L’、‘R’ 和 ‘X’

提示： 可以将 L 和 R 视为水平线上的人，X 是空间。人不能相互穿越，也不能从 XRX 变为 RXX。

解题思路

解题思路

这道题的核心在于理解移动规则：

  • “XL” → “LX”：L 可以向左移动穿过 X
  • “RX” → “XR”：R 可以向右移动穿过 X

关键观察：

  1. 相对顺序不变：去除所有 X 后，L 和 R 的相对顺序必须保持不变
  2. 移动方向限制：L 只能向左移动，R 只能向右移动
  3. 位置约束：在 start 中的每个 L 在 result 中的位置不能更右，每个 R 在 result 中的位置不能更左

解法分析： 使用双指针分别遍历 start 和 result，跳过 X 字符，只比较 L 和 R：

  1. 首先检查去除 X 后的字符序列是否相同
  2. 然后检查每个字符的位置是否满足移动约束

算法步骤：

  1. 使用两个指针 i 和 j 分别指向 start 和 result
  2. 跳过 X 字符，找到下一个 L 或 R
  3. 比较字符是否相同，如果不同则返回 false
  4. 检查位置约束：L 在 result 中不能比在 start 中更右，R 在 result 中不能比在 start 中更左
  5. 继续处理直到遍历完成

代码实现

class Solution {
public:
    bool canTransform(string start, string result) {
        int n = start.length();
        int i = 0, j = 0;
        
        while (i < n || j < n) {
            // 跳过start中的X
            while (i < n && start[i] == 'X') i++;
            // 跳过result中的X
            while (j < n && result[j] == 'X') j++;
            
            // 如果一个到达末尾，另一个也必须到达末尾
            if (i == n && j == n) return true;
            if (i == n || j == n) return false;
            
            // 字符必须相同
            if (start[i] != result[j]) return false;
            
            // 检查位置约束
            if (start[i] == 'L' && i < j) return false; // L不能向右移动
            if (start[i] == 'R' && i > j) return false; // R不能向左移动
            
            i++;
            j++;
        }
        
        return true;
    }
};

class Solution:
    def canTransform(self, start: str, result: str) -> bool:
        n = len(start)
        i = j = 0
        
        while i < n or j < n:
            # 跳过start中的X
            while i < n and start[i] == 'X':
                i += 1
            # 跳过result中的X
            while j < n and result[j] == 'X':
                j += 1
            
            # 如果一个到达末尾，另一个也必须到达末尾
            if i == n and j == n:
                return True
            if i == n or j == n:
                return False
            
            # 字符必须相同
            if start[i] != result[j]:
                return False
            
            # 检查位置约束
            if start[i] == 'L' and i < j:
                return False  # L不能向右移动
            if start[i] == 'R' and i > j:
                return False  # R不能向左移动
            
            i += 1
            j += 1
        
        return True

public class Solution {
    public bool CanTransform(string start, string result) {
        int n = start.Length;
        int i = 0, j = 0;
        
        while (i < n || j < n) {
            // 跳过start中的X
            while (i < n && start[i] == 'X') i++;
            // 跳过result中的X
            while (j < n && result[j] == 'X') j++;
            
            // 如果一个到达末尾，另一个也必须到达末尾
            if (i == n && j == n) return true;
            if (i == n || j == n) return false;
            
            // 字符必须相同
            if (start[i] != result[j]) return false;
            
            // 检查位置约束
            if (start[i] == 'L' && i < j) return false; // L不能向右移动
            if (start[i] == 'R' && i > j) return false; // R不能向左移动
            
            i++;
            j++;
        }
        
        return true;
    }
}

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

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：O(n)，其中 n 是字符串长度，每个字符最多被访问一次
  • 空间复杂度：O(1)，只使用了常数额外空间

相关题目