【2022-10-02每日一题】777. 在LR字符串中交换相邻字符[Medium]
2022-10-02
3分钟阅读时长
2022-10-02每日一题：777. 在LR字符串中交换相邻字符
难度：Medium
标签：双指针 、 字符串
在一个由 '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'。
方法一：
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
每次移动操作将 “XL" 替换成 “LX"，或将 “RX" 替换成“XR"，等价于如下操作：
如果一个字符 ‘L’ 左侧的相邻字符是 ‘X’，则将字符 ‘L’ 向左移动一位，将其左侧的 ‘X’ 向右移动一位；
如果一个字符 ‘R’ 右侧的相邻字符是 ‘X’，则将字符 ‘R’ 向右移动一位，将其右侧的 ‘X’ 向左移动一位。
// 写法一
func canTransform(start, end string) bool {
i, j, n := 0, 0, len(start)
for i < n && j < n {
for i < n && start[i] == 'X' {
i++
}
for j < n && end[j] == 'X' {
j++
}
if i < n && j < n {
if start[i] != end[j] {
return false
}
c := start[i]
if c == 'L' && i < j || c == 'R' && i > j {
return false
}
i++
j++
}
}
for ; i < n; i++ {
if start[i] != 'X' {
return false
}
}
for ; j < n; j++ {
if end[j] != 'X' {
return false
}
}
return true
}
// 写法二
func canTransform(start string, end string) bool {
i, j, n := 0, 0, len(start)
for i < n || j < n {
for i < n && start[i] == 'X' {
i++
}
for j < n && end[j] == 'X' {
j++
}
if i == n || j == n {
return i == j
}
if start[i] != end[j] {
return false
}
// L 不能右移， R 不能左移
if start[i] == 'L' && i < j || start[i] == 'R' && i > j{
return false
}
i++
j++
}
return i == j
}
php
class Solution {
/**
* @param String $start
* @param String $end
* @return Boolean
*/
function canTransform($start, $end) {
$startIndex = $endIndex = 0;
$n = strlen($start);
while ($startIndex < $n || $endIndex < $n) {
while ($startIndex < $n && $start[$startIndex] == 'X') $startIndex++;
while ($endIndex < $n && $end[$endIndex] == 'X') $endIndex++;
if ($startIndex < $n && $endIndex < $n) {
if ($start[$startIndex] == $end[$endIndex]) {
if ($start[$startIndex] == 'L' && $startIndex < $endIndex) break;
if ($start[$startIndex] == 'R' && $startIndex > $endIndex) break;
$startIndex++;
$endIndex++;
}
else break;
} else {
if ($startIndex < $n && $start[$startIndex] != 'X') break;
if ($endIndex < $n && $end[$endIndex] != 'X') break;
}
}
return ($startIndex == $endIndex) && ($startIndex == $n);
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是字符串 start 和 end 的长度。需要遍历两个字符串各一次。
空间复杂度：O(1)。只需要使用常量的额外空间。