关于后端:777-在LR字符串中交换相邻字符-双指针运用题

3次阅读

共计 1276 个字符，预计需要花费 4 分钟才能阅读完成。

这是 LeetCode 上的 777. 在 LR 字符串中替换相邻字符 ，难度为中等。

Tag :「双指针」

在一个由 'L' ,'R' 和 'X' 三个字符组成的字符串（例如 "RXXLRXRXL"）中进行挪动操作。

一次挪动操作指用一个 "LX" 替换一个 "XL"，或者用一个 "XR" 替换一个 "RX"。

现给定起始字符串 start 和完结字符串 end，请编写代码，当且仅当存在一系列挪动操作使得 start 能够转换成 end 时，返回 True。

示例 :

输出: start = "RXXLRXRXL", end = "XRLXXRRLX"

输入: True

解释:
咱们能够通过以下几步将 start 转换成 end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

提醒：

$1 <= len(start) = len(end) <= 10000$
start 和 end 中的字符串仅限于 'L', 'R' 和 'X'

依据题意，咱们每次挪动要么是将 XL 变为 LX，要么是将 RX 变为 XR，而该两者操作可别离看做将 L 越过多个 X 向左挪动，将 R 越过多个 X 向右挪动。

因而在 start 和 end 中序号雷同的 L 和 R 必然满足坐标性质：

序号雷同的 L : start 的下标不小于 end 的下标（即 L 不能往右挪动）
序号雷同的 R : start 的下标不大于 end 的下标（即 R 不能往左挪动）

其中「序号」是指在 LR 字符串中呈现的绝对程序。

代码：

class Solution {public boolean canTransform(String start, String end) {int n = start.length(), i = 0, j = 0;
        while (i < n || j < n) {while (i < n && start.charAt(i) == 'X') i++;
            while (j < n && end.charAt(j) == 'X') j++;
            if (i == n || j == n) return i == j;
            if (start.charAt(i) != end.charAt(j)) return false;
            if (start.charAt(i) == 'L' && i < j) return false;
            if (start.charAt(i) == 'R' && i > j) return false;
            i++; j++;
        }
        return i == j;
    }
}