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
字符可以向右移动到空位”
那么可以在考虑该移动策略的前提下,枚举所有可能。对于相同位置的字符,有:
起始字符 | 结束字符 | 结果 |
---|---|---|
L |
L |
可以转换 |
L |
R |
无法转换 |
L |
X |
无法转换 |
R |
L |
无法转换 |
R |
R |
可以转换 |
R |
X |
可能可以转换 |
X |
L |
可能可以转换 |
X |
R |
无法转换 |
X |
X |
可以转换 |
也即,实际上是需要考虑两种情况即可R
到X
和X
到L
以R
到X
为例,如果R
存在右移的可能,那么必会留下一个X
(空位)。因此只需要考虑是否可以移动即可。如果R
想要移动,那么右侧必然存在一个X
,且到这个X
中间不能存在L
。这样只需要将中间所有的R
右移一位即可。
直接运行该算法,最坏情况下时间复杂度应该是 ,空间复杂度为
最坏时,可能会存在诸如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; }