LeetCode_双指针_中等_777.在LR字符串中交换相邻字符

朴灿烈づ我的快乐病毒、 2023-10-07 20:07 33阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

在一个由 ‘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’。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/swap-adjacent-in-lr-string

## 2.思路 ##

（1）双指针  
思路参考[该 LeetCode 用户题解][LeetCode]。

① 如果直接像题目中描述的那样，**真正在代码层面对 start 进行移动操作，代码将会变得比较复杂**。  
② 仔细观察题目，题目允许的移动操作只有两种：即用一个 “LX” 替换一个 “XL”，或者用一个 “XR” 替换一个 “RX”。而如果多次进行这两种移动操作，其实就将它们分别看作**将 L 越过多个 X 向左移动，将 R 越过多个 X 向右移动**。

例如，start = "RXXXXLX"，经过多次移动之后可以变为 "XXXXRLX"，同理 "XRXXXXL" 也可以变为 "XRLXXXX"

③ 所以使得 start 可以转换成 end，对于 start 和 end 中出现的相对顺序相同的 L 和 R的下标必须满足一定的条件：  
1）出现的相对顺序相同的 L：start 中的下标要大于等于 end 中的下标，即 start 中的 L 不能向右移动；  
2）出现的相对顺序相同的 R：start 中的下标要小于等于 end 中的下标，即 start 中的 R 不能向左移动；

例如，start = "XXXRR"，end = "XXRXR"，第一个出现的相对顺序相同的 R 的下标分别为 3 和 2，此时 3 > 2，而 start 中的 R 不能向左移动，
    因此 start 不能转换成 end。

## 3.代码实现（Java） ##

//思路1————双指针
    class Solution {
        
        public boolean canTransform(String start, String end) {
        
            int length = start.length();
            //指针 i 初始时指向 start 的第一个字符
            int i = 0;
            //指针 j 初始时指向 end 的第一个字符
            int j = 0;
            while (i < length || j < length) {
        
                // 两指针均向右移动，直到遇到第一个不为 'X' 的字符
                while (i < length && start.charAt(i) == 'X') {
        
                    i++;
                }
                while (j < length && end.charAt(j) == 'X') {
        
                    j++;
                }
                if (i == length || j == length) {
        
                    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;
        }
    }

[LeetCode]: https://leetcode.cn/problems/swap-adjacent-in-lr-string/solution/by-ac_oier-ye71/