LC 777. 在LR字符串中交换相邻字符

题目描述

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

在一个由 'L' ,'R''X' 三个字符组成的字符串(例如 "RXXLRXRXL")中进行移动操作。

一次移动操作指用一个 "LX" 替换一个 "XL",或者用一个 "XR" 替换一个 "RX"

现给定起始字符串 start 和结束字符串 end,请编写代码,当且仅当存在一系列移动操作使得 start 可以转换成 end 时, 返回 True

示例 :

1
2
3
4
5
6
7
8
9
10
11
输入: start = "RXXLRXRXL", end = "XRLXXRRLX"

输出: True

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

提示:

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

双指针

根据题意,我们每次移动要么是将 XL 变为 LX,要么是将 RX 变为 XR,而该两者操作可分别看做将 L 越过多个 X 向左移动,将 R 越过多个 X 向右移动。

因此在 startend 中序号相同的 LR 必然满足坐标性质:

  1. 序号相同的 L : start 的下标不小于 end 的下标(即 L 不能往右移动)
  2. 序号相同的 R : start 的下标不大于 end 的下标(即 R 不能往左移动)

其中「序号」是指在 LR 字符串中出现的相对顺序。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool canTransform(string start, string end) {
int n = start.size();
int i = 0, j = 0;
while (i < n || j < n) {
while (i < n && start[i] == 'X') i++;
while (j < n && end[j] == 'X') j++;
if (i == n || j == n) return i == j;
if (start[i] != end[j]) return false;
if (start[i] == 'L' && i < j) return false;
if (start[i] == 'R' && i > j) return false;
i++; j++;
}
return i == j;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def canTransform(self, start: str, end: str) -> bool:
i, j, n = 0, 0, len(start)
while i < n or j < n:
while i < n and start[i] == 'X': i += 1
while j < n and end[j] == 'X': j += 1
if i == n or j == n: return i == j
if start[i] != end[j]: return False
if start[i] == 'L' and i < j: return False
if start[i] == 'R' and i > j: return False
i, j = i + 1, j + 1
return i == j

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function canTransform(start: string, end: string): boolean {
let n = start.length;
let 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;
};

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.777 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。