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

桃扇骨 2024-04-03 08:19 72阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[每日一道LeetCode][LeetCode]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

**目录**

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

解答思路：双指针法

分析：

Java解题代码：

--------------------

## **题目描述：在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的左边！！这样思路就清晰一点。我们拿示例画个草图理解一下：

![ed48bc3ac3cf4e0fa310211a8fb05f9b.png][]

当位置不对应的时候，直接返回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;
    
        }
    }

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

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/34991313a57a4e628145f9cb83deab7b.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[LeetCode]: https://blog.csdn.net/m0_67995737/category_11942571.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[ed48bc3ac3cf4e0fa310211a8fb05f9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9c87a800484243248f0049df7fdcc466.png