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

思路

如果一个start可以完成到end的转换，那么，两个字符串中L和R的相对位置一定会保持一致。

可以在start和end上分别各自定义指针i和j，跳过X直到第一个L或者R出现，此时判断s[i]和s[j]是否相等，如果不相等则不满足相对顺序，无法完成转换。

XL被LX替换，RX被XR替换，则意味着：

  • 如果能完成转换，最终end中第N个L的下标，只能小于或等于start中第N个L的下标，即L只允许左移或原地停留。
  • 如果能完成转换，最终end中第M个R的下标，只能大于或等于start中第M个R的下标，即R只允许右移或原地停留。

思路递推

以题目中的start = “RXXLRXRXL”, end = “XRLXXRRLX"为例：

  • 找到第一个不为X的下标，此时i=0，j=1。
  • 判断s[i] == s[j]，此时结果为true。
  • 判断i和j的顺序，由于两字符均为R，R只允许右移或原地停留，即j >= i，所以s[i]可以被转换至s[j]，即XR替换RX。
  • 找到第二个不为X的下标，此时i=3,j=2。
  • 判断s[i] == s[j]，此时结果为true。
  • 判断i和j的顺序，由于两字符均为L，L只允许左移或原地停留，即j <= i，所以s[i]可以被转换至s[j]，即LX替换XL。
  • 找到第三个不为X的下标，此时i=4,j=5。
  • 判断s[i] == s[j]，此时结果为true。
  • 判断i和j的顺序，由于两字符均为R，R只允许右移或原地停留，即j >= i，所以s[i]可以被转换至s[j]，即XR替换RX。
  • 找到第四个不为X的下标，此时i=6,j=6。
  • 判断s[i] == s[j]，此时结果为true。
  • 判断i和j的顺序，由于两字符均为R，R只允许右移或原地停留，即j >= i，所以s[i]可以被转换至s[j]，即原地停留。
  • 找到第五个不为X的下标，此时i=8,j=7。
  • 判断s[i] == s[j]，此时结果为true。
  • 判断i和j的顺序，由于两字符均为L，L只允许左移或原地停留，即j <= i，所以s[i]可以被转换至s[j]，即LX替换XL。
  • 此时i到达末尾，完成搜索，判断i是否和j相等，只有两个指针到达同样的位置，才能完成转换。

代码实现：

public static boolean canTransform(String start, String end) {
        int length = start.length();
        //定义双指针i和j，分别指向start和end
        //1.分别找到start和end中第一个不为X的字符s[i]和s[j]
        //2.判断s[i]是否和s[j]相等，若不相等，则不满足相对顺序，无法完成转换
        //3.判断s[j]的顺序：L字符只允许向左转换，R字符只允许向右转换
        //同时需要注意：start和end全由X组成的情况
        int i = 0,j = 0;
        while (i < length || j < length){
            while (i < length && start.charAt(i) == 'X')
                //找到start中第一个不为X的字符位置
                i++;
            while (j < length && end.charAt(j) == 'X')
                //找到end中第一个不为X的字符位置
                j++;
            if (i == length || j == length)
                //任意一边指针到头，说明当前字符串全由X组成，则另一个字符串也应该全由X组成才能完成转换
                return i == j;
            if (start.charAt(i) != end.charAt(j))
                //判断s[i]是否和s[j]相等，若不相等，则不满足相对顺序，无法完成转换
                return false;
            if (start.charAt(i) == 'L' && i < j)
                //L字符只允许向左转换，即转换后的下标j不应该大于i
                return false;
            if (start.charAt(i) == 'R' && i > j)
                //R字符只允许向左转换，即转换后的下标j不应该小于i
                return false;
            i++;
            j++;
        }
        return i == j;
    }

    public static void test(){
        System.out.println(canTransform("RXXLRXRXL","XRLXXRRLX"));
        System.out.println(canTransform("RXXLRXRXL","XRXLXRLLX"));
    }