[LeetCode]Swap Adjacent in LR String

这道题我们可以观察到几点：

1. L只能向左移动
2. R只能向右移动
3. L与L之间，R与R之间，L与R之间不可以相互cross

所以我们只需要用双指针的方法，每次找到不是X的char，比较两个char是否相等。如果相等都是L的话，那么L不能够在原string中的位置的右边，R不能在原string位置中的左边。时间复杂度O(n)，常数空间，代码如下：

	class Solution {
	public:
	bool canTransform(string start, string end) {
	int len = start.size();
	if (len != end.size())return false;
	int i = 0, j = 0;
	while (i < len || j < len)
	{
	while (i < len && start[i] == 'X')++i;
	while (j < len && end[j] == 'X')++j;
	if (i >= len || j >= len)break;
	char s = start[i], e = end[j];
	if (s != e)return false;
	if (s == 'L' && i < j || s == 'R' && i > j)return false;
	++i;
	++j;
	}
	return i == j;
	}
	};

view raw Swap Adjacent in LR String.cpp hosted with ❤ by GitHub