class Solution {
public:
bool canTransform(string start, string end) {
}
};
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'。原站题解
javascript 解法, 执行用时: 60 ms, 内存消耗: 41.2 MB, 提交时间: 2023-06-27 17:20:21
/**
* @param {string} start
* @param {string} end
* @return {boolean}
*/
var canTransform = function(start, end) {
const n = start.length;
let i = 0, j = 0;
while (i < n && j < n) {
while (i < n && start[i] === 'X') {
i++;
}
while (j < n && end[j] === 'X') {
j++;
}
if (i < n && j < n) {
if (start[i] !== end[j]) {
return false;
}
const c = start[i];
if ((c === 'L' && i < j) || (c === 'R' && i > j)) {
return false;
}
i++;
j++;
}
}
while (i < n) {
if (start[i] !== 'X') {
return false;
}
i++;
}
while (j < n) {
if (end[j] !== 'X') {
return false;
}
j++;
}
return true;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2.7 MB, 提交时间: 2023-06-27 17:14:08
func canTransform(start, target string) bool {
if strings.ReplaceAll(start, "X", "") != strings.ReplaceAll(target, "X", "") {
return false
}
j := 0
for i, c := range start {
if c != 'X' {
for target[j] == 'X' {
j++
}
if i != j && c == 'L' != (i > j) {
return false
}
j++
}
}
return true
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 7.2 MB, 提交时间: 2023-06-27 17:13:45
class Solution {
public:
bool canTransform(string &start, string &target) {
auto s = start, t = target;
s.erase(remove(s.begin(), s.end(), 'X'), s.end());
t.erase(remove(t.begin(), t.end(), 'X'), t.end());
if (s != t) return false;
for (int i = 0, j = 0; i < start.length(); ++i) {
if (start[i] == 'X') continue;
while (target[j] == 'X') ++j;
if (i != j && (start[i] == 'L') != (i > j)) return false;
++j;
}
return true;
}
};
java 解法, 执行用时: 18 ms, 内存消耗: 43.3 MB, 提交时间: 2023-06-27 17:13:07
class Solution {
public boolean canTransform(String start, String target) {
if (!start.replaceAll("X", "").equals(target.replaceAll("X", ""))) return false;
for (int i = 0, j = 0; i < start.length(); ++i) {
if (start.charAt(i) == 'X') continue;
while (target.charAt(j) == 'X') ++j;
if (i != j && (start.charAt(i) == 'L') != (i > j)) return false;
++j;
}
return true;
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-27 17:12:39
'''
替换操作可以转换成，把 L 往左移动（需要左边是 X），把 R 往右移动（需要右边是 X）。
那么无论怎么移动，由于 L 和 R 无法互相穿过对方，那么去掉 X 后的剩余字符应该是相同的，否则返回 false。
然后用双指针遍历 start[i] 和 target[j]，分类讨论：
如果当前字符为 L 且 i<j，那么这个 L 由于无法向右移动，返回 false；
如果当前字符为 R 且 i>j，那么这个 R 由于无法向左移动，返回 false。
遍历完，若中途没有返回 false 就返回 true。
'''
class Solution:
def canTransform(self, start: str, target: str) -> bool:
if start.replace('X', '') != target.replace('X', ''): return False
j = 0
for i, c in enumerate(start):
if c == 'X': continue
while target[j] == 'X': j += 1
if i != j and (c == 'L') != (i > j): return False
j += 1
return True