本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

LeetCode2337. 移动片段得到字符串

给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 ‘L’、‘R’ 和 ‘’ 组成，其中：
字符 ‘L’ 和 ‘R’ 表示片段，其中片段 ‘L’ 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 ‘R’ 只有在其右侧直接存在一个 空位 时才能向 右 移动。
字符 '’ 表示可以被 任意 ‘L’ 或 ‘R’ 片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
示例 1：
输入：start = “L__R__R”, target = “L______RR”
输出：true
解释：可以从字符串 start 获得 target ，需要进行下面的移动：

• 将第一个片段向左移动一步，字符串现在变为 “L___R__R_” 。
• 将最后一个片段向右移动一步，字符串现在变为 “L___R___R” 。
• 将第二个片段向右移动三步，字符串现在变为 “L______RR” 。
  可以从字符串 start 得到 target ，所以返回 true 。
  示例 2：
  输入：start = “R_L_”, target = “__LR”
  输出：false
  解释：字符串 start 中的 ‘R’ 片段可以向右移动一步得到 “RL” 。
  但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
  示例 3：
  输入：start = “R", target = "R”
  输出：false
  解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。
  提示：
  n == start.length == target.length
  1 <= n <= 10⁵
  start 和 target 由字符 ‘L’、‘R’ 和 ‘_’ 组成

双指针

无法交换两个相邻非_，LR无法变成RL，RL无法变成LR。
删除_后，start和target必须相等，否则直接返回fasle。
i,j依次指向第k个start的非_，第k个target的非_。
如果start[i] != target[j]，返回false。
如果是L, i >= j，否则返回false。
如果是R,i <= j，否则返回false。
返回i,j是否同时结束。

代码

核心代码

class Solution {
		public:
			bool canChange(string start, string target) {
				int i = 0, j = 0;
				while (true) {
					while ((i < start.length()) && (start[i] == '_')) { i++; }
					while ((j < target.length()) && (target[j] == '_')) { j++; }
					if ((i == start.length()) && (j == target.length())) { return true; }
					if ((i == start.length()) || (j == target.length())) { return false; }
					if (start[i] != target[j]) { return false; }
					if ('L' == start[i])
					{
						if (i < j) { return false; }
					}
					else {
						if (i > j) { return false; }
					}				
					i++, j++;
				}
				return false;
			}
		};

单元测试

string start, target;
		TEST_METHOD(TestMethod11)
		{
			start = "_L__R__R_", target = "L______RR";
			auto res = Solution().canChange(start, target);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod12)
		{
			start = "R_L_", target = "__LR";
			auto res = Solution().canChange(start, target);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod13)
		{
			start = "_R", target = "R_";
			auto res = Solution().canChange(start, target);
			AssertEx(false, res);
		}