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

题目描述

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

题解

暴力解

首先，稍微画一下各种情况，可以发现一种需要特别警惕的情景：RRXX可以被转换成RXRX、XRRX、XRXR、XXRR这些状态。
同理，L也存在类似的情况

将这种情景推广，用更为准确的情况描述，就是“X表示空位，L字符可以向左移动到空位，R字符可以向右移动到空位”

那么可以在考虑该移动策略的前提下，枚举所有可能。对于相同位置的字符，有：

也即，实际上是需要考虑两种情况即可R到X和X到L

以R到X为例，如果R存在右移的可能，那么必会留下一个X（空位）。因此只需要考虑是否可以移动即可。如果R想要移动，那么右侧必然存在一个X，且到这个X中间不能存在L。这样只需要将中间所有的R右移一位即可。

直接运行该算法，最坏情况下时间复杂度应该是 O(n2)O(n^2)，空间复杂度为 O(1)O(1)

最坏时，可能会存在诸如RRRRRRRRRRRRRRRRRRRRRRRXXXXXX……的形式，每一个R都需要遍历后面所有的R

最优解

再次看上面的结论，如果我现在是R到X的情况，我必须要确保找到下一个X之前不能有L。这时候去考虑另一个串的情况，由于在这个过程中，涉及的都是R的右移，因此至少要确保对应数目的R出现前，不能有L，否则无法一一对应。

也即，在不考虑X的情况下，将相邻的R和L压缩，两个串将会得到相同的结果。
如RXXLRXRXL压缩有应该是R(1)L(1)R(2)L(1)那么其可以转换成的目标串，压缩后必然也是R(1)L(1)R(2)L(1)
可以视为，去除X后，两个串相同。

接下来考虑L和R的特点：R只允许右移，L只允许左移。
因此，对于串XRR和RXR，尽管压缩后都是R(2)但是却无法转换成功。也即，起始串对应位置的R必须在目标串左侧。L同理。

总结下上述规律，只需要判断在两个串中，非X字符位置是否满足：

• 字符相同
• R 字符在起始串下标小于等于结束串
• L 字符在结束串下表大于等于结束串

接下来要做的就是判定好边界情况

应该如何思考

如果多画一画，应该很容易发现L左移和R右移的规律。
可能再多手画几组数据，可能会有想到上面压缩的思路，但是很容易会被大量测试用例给否掉。

似乎如果将转换关系连线起来，会更易于理解，发现规律

如RXXLRXRXLRRX到XRLXXRRLXXRR的转换（可以看出，L、R转换关系不交叉且拥有方向性）

代码

暴力解

bool canTransform(char * start, char * end){
    char* a = start;
    char* b = end;
    while(*a != '\0') {
        // printf("%c %d\n", *a, *a);
        if (*a == 'R' && *b == 'X') {
            char* temp = a;
            while (*temp != '\0') {
                ++temp;
                if (*temp == 'L') return false;
                if (*temp == 'X') {
                    *temp = 'R';
                    break;
                }
            }
            if (*temp == '\0') return false;
            *a = 'X';
        } else if (*a == 'X' && *b == 'L') {
            char* temp = a;
            while (*temp != '\0') {
                ++temp;
                if (*temp == 'R') return false;
                if (*temp == 'L') {
                    *temp = 'X';
                    break;
                }
            }
            if (*temp == '\0') return false;
            *a = 'L';
        } else if (*a != *b) return false;
        ++a; ++b;
    }
    return true;
}

最优解

bool canTransform(char * start, char * end){
    int i = 0;
    int j = 0;
    while(start[i] != '\0' && end[j] != '\0') {
        // 找到第一个非 X 字符
        while (start[i] == 'X') ++i;
        while (end[j] == 'X') ++j;

        bool iend = start[i] == '\0';
        bool jend = end[j] == '\0';
        // 两者直接到末尾，说明全是 X 可以转换
        if (iend && jend) return true;
        // 存在一个到末尾，另一个未到末尾，说明个数不同，不能转换
        if (iend ^ jend) return false;

        // 如果对应的字符不同，说明无法转换
        // 如果起始串 R 位置大于目标串，说明无法转换
        // 如果起始串 L 位置小于目标串，说明无法转换
        if (
            start[i] != end[j] || 
            (start[i] == 'R' && i > j) || 
            (start[i] == 'L' && i < j)
        ) return false;
        
        i++; j++;
    }

    // 处理末尾部分
    while (start[i] != '\0') if (start[i++] != 'X') return false;
    while (end[j] != '\0') if (end[j++] != 'X') return false;

    return true;
}