在LR字符串中交换相邻字符(Leetcode 777)

题目分析

   看到这种没有明显思路的题目，我们需要做的是进行模拟，在模拟的过程中发现答案。

双指针

在模拟的时候，我们发现XL可以替换成LX，那么L只能向左移动，同理RX可以替换成XR，那么R只能向右移动，说明end的L必须要在start对应L的左边，R必须要在start对应R的右边。且R和X不能交换，说明R和L的相对关系是保持不变的，不可能从RL变成LR。

因此思路是双指针，一个指针指向start的当前元素，一个指针指向end的当前元素。如果发现是X，则继续向后寻找到不为X的元素。如果两个元素不相等，则说明会出现RL和LR的情况，return false。否则如果元素是L，看看end指针是否在start指针的左边，如果元素是R，看看end指针是否在start指针的右边。

当某个指针移动到最后时，另一个指针如果后面均为X，说明是成立的，如果后面存在R或者L，说明无法正确匹配，return false。当所有条件均满足，return true。

算法的**时间复杂度为O(n)，空间复杂度为O(1)**。

class Solution {
    public boolean canTransform(String start, String end) {
        int n = start.length();
        int left = 0;
        int right = 0;
        while (left < n && right < n) {
            while (left < n && start.charAt(left) == 'X') {
                left++;
            }
            while (right < n && end.charAt(right) == 'X') {
                right++;
            }
            if (left == n || right == n) {
                break;
            }
            char leftC = start.charAt(left);
            char rightC = end.charAt(right);
            if (leftC != rightC) {
                return false;
            }
            if ((leftC == 'R' && left > right) || (leftC == 'L' && left < right)) {
                return false;
            }
            left++;
            right++;
        }
        while (left < n) {
            if (start.charAt(left) != 'X') {
                return false;
            }
            left++;
        }
        while (right < n) {
            if (end.charAt(right) != 'X') {
                return false;
            }
            right++;
        }
        return true;
    }
}

刷题总结

  本题的难度不小，主要是看小伙伴能否找到关键的一句话。end的L必须要在start对应L的左边，R必须要在start对应R的右边，R和L的相对关系是保持不变的。