题目描述

在一个由 'L' , 'R''X' 三个字符组成的字符串(例如 "RXXLRXRXL")中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL",或者用一个 "XR" 替换一个 "RX"。现给定起始字符串 start 和结束字符串 end,请编写代码,当且仅当存在一系列移动操作使得 start 可以转换成 end 时, 返回 True

示例 :

1
2
3
4
5
6
7
8
9
输入: start = "RXXLRXRXL", end = "XRLXXRRLX"
输出: True
解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

提示:

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

来源:力扣(LeetCode)

题解

通过题目描述可知,start 字符串中的 "XL" 换成 "LX""RX" 换成 "XR",也就是 'L' 左移,'R' 右移,使得 start 转换成为 end 。仔细思考将会发现,如果可以转换,两个字符串中的 'L''R' 的相对位置不会放生变化,并且顺序和数量一致。

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean canTransform(String start, String end) {
int n = start.length();
int 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) {
if (start.charAt(i) != end.charAt(j)) return false;
// XL -> LX
if (start.charAt(i) == 'L' && i < j) return false;
// RX -> XR
if (start.charAt(i) == 'R' && i > j) return false;
i++;
j++;
}
}
while (i < n) if (start.charAt(i++) != 'X') return false;
while (j < n) if (end.charAt(j++) != 'X') return false;
return true;
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

submissions-2022100201

双指针(精简)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean canTransform(String start, String end) {
int n = start.length();
int 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++;
// 注意 while 循环的条件是 i < n || j < n, 是或(||)而不是与(&&)
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 true;
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

submissions-2022100202

Q:为什么操作 charAt() 方法效率低于操作 toCharArray() 方法获得的字符数组?

A: 虽然 charAt() 方法也是操作 String 对象的内置字符数组,但是中间夹杂了其他的一些判断,所以导致效率低。

参考资料

__END__