【LeetCode】在 LR 字符串中交换相邻字符 Java 题解

作者：Albert

2022 年 10 月 02 日
北京
本文字数：1080 字
阅读完需：约 4 分钟

题目描述

在一个由 '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
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/swap-adjacent-in-lr-string著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是字符串题目，题目要求判断在 LR 字符串中交换相邻字符是否可以完成转换。题目中的 LR，我们也可以理解成为 left, right。这样看更容易理解。
由于每次需要交换的指定字符，首先容易想到的是采取模拟的方法。我们可以采用 BFS 的方法，模拟每次的变化。由于我们需要记录每一次的变化情况，我们一般是使用 StringBuilder，在使用 StringBuilder 类的优点是，每次都会对 StringBuilder 对象本身进行操作，而不是生成新的对象。这样可以节省大量的空间，提升我们算法程序的代码执行效率。经过 BFS 的编写，发现字符重复计算过多，不能通过所有测试 case。
再次分析题目，题目不需要我们给出转换的路径，只需要判断是否能够满足转换，因此，我们不需要枚举每一个中间计算结果。对于操作"LX"替换一个"XL",是将"L"移动到了"X"的左边。操作"XR"替换一个"RX"是将"R"移动到了"X"的右边。我们只需要判断 L 和 R 在 start 和 end 中的相对位置即可。当 L 相同的时候，start 中 L 的下标不小于 end 中 L 的下标。当 R 相同的时候，start 中 R 的下标不大于 end 中 R 的下标。
具体实现代码如下，供参考。

通过代码

class Solution {    public boolean canTransform(String start, String end) {        int n = start.length(), i = 0, j = 0;        while (i < n || j < n) {            while (i < n && start.charAt(i) == 'X') i++;            while (j < n && end.charAt(j) == 'X') j++;            if (i == n || j == n) return i == j;            if (start.charAt(i) != end.charAt(j)) return false;            if (start.charAt(i) == 'L' && i < j) return false;            if (start.charAt(i) == 'R' && i > j) return false;            i++; j++;        }        return i == j;    }}