LeetCode竞赛题目—在LR字符串中交换相邻字符

作者：渴望力量的土狗

博客主页：渴望力量的土狗的博客主页

专栏：每日一道LeetCode

工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧

题目描述：在LR字符串中交换相邻字符

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动A操作指用一个"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'

。

解答思路：双指针法

这个题目说实话，会的是感觉真会，不会的是想破脑袋也解不出来（当然还伴随头疼哈哈哈），我在拿到这个题目的时候想到了双指针法，当然，光是想到方法还不行，还必须实现出来（不瞒你们说，这题我解了将近1个小时哈哈哈）好，废话不多说，开始我们的思路！

分析：

拿到题目时，首先要明确我们的目标-->用一系列操作使得start可以转换成end时， 返回True。

那么操作是什么呢？"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"，看到这里我们还是一脸懵逼，别急，我们接着看这个操作的内容，"LX"替换"XL"说明了什么？说明start中的L必须在对应的end中L的右边，那么"XR"替换"RX"是不是就说明了start中的R必须在end中R的左边！！这样思路就清晰一点。我们拿示例画个草图理解一下：

当位置不对应的时候，直接返回false，对应的情况下我们就可以想到用双指针来比较其位置，当我们的两个指针指向内容都是R或者L的时候记录其下标，然后进行比较，比较什么？前面说过，start中的L位置必须比end的大，也就是假如我们定义i指针指向start。j指向end的时候，当i指向的值是L的时候，i必须要大于j，否则返回false，同理，当i指向的值是R的时候，i必须小于j，否则返回false。如果执行跳出了循环，则说明所有的条件都满足了，返回true！解答完毕！，详细情况请看解题代码部分。

Java解题代码：

class Solution {
    public boolean canTransform(String start, String end) {

        int i=0;
        int j=0;
        int len=start.length();
        //如果去掉所有X后不能相等就false
        if(!start.replaceAll("X","").equals(end.replaceAll("X","")))
        return false;
        //相等之后判断是否满足条件
        while(i<len&&j<len){

            while(i<len&&start.charAt(i)=='X'){
                i++;
            }
            while(j<len&&end.charAt(j)=='X'){
                j++;
            }

            //进行判断，如果是L,则i必须>j
            //如果是R，则i必须小于j
            if(i<len&&j<len&&start.charAt(i)=='L'&&i<j){
                return false;
            }
            if(i<len&&j<len&&start.charAt(i)=='R'&&i>j){
                return false;
            }
            i++;
            j++;
        }

        return true;

    }
}

“ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！