题目描述

在一个由 '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__