LeetCode777-在LR字符串中交换相邻字符

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/swap-adjacent-in-lr-string/

中文链接：https://leetcode-cn.com/problems/swap-adjacent-in-lr-string/

题目详述

在一个由 ‘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. 1 <= len(start) = len(end) <= 10000。
  2. start和end中的字符串仅限于’L’, ‘R’和’X’。

题目详解

  • 实际上替换的规则是：L 可以穿过 X 向左移动，R 可以穿过 X 向右移动。
  • 首先两个字符串长度不等肯定不能转换。
  • 能从 start 转换到 end ，start 和 end 去掉所有 X 的字符串是相同的。
  • 并且 start 与 end 匹配的字符为 L 时，start 中的 L 位置一定不能在 end 中位置的左边，否则就违背了 L 只能向左移动的原则；start 与 end 匹配的字符为 R 时，start 中的 R 位置一定不能在 end 中位置的右边，否则就违背了 R 只能向右移动的原则。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class LeetCode_00777 {

    public boolean canTransform(String start, String end) {
        // 长度不等肯定不能转换
        if (start.length() != end.length()) {
            return false;
        }
        int i = 0, j = 0;
        while (true) {
            // 跳过 X
            while (i < start.length() && start.charAt(i) == 'X') {
                ++i;
            }
            while (j < end.length() && end.charAt(j) == 'X') {
                ++j;
            }
            // 同时到达末尾返回 true
            if (i == start.length() && j == start.length()) {
                return true;
            }
            // 只有一个到达末尾返回 false
            if (i == start.length() || j == start.length() || start.charAt(i) != end.charAt(j)) {
                return false;
            }
            // 要满足“L 只能往左走，R 只能往右走”的条件
            if (start.charAt(i) == 'L' && i < j || start.charAt(i) == 'R'  && i > j) {
                return false;
            }
            ++i;
            ++j;
        }
    }
}