777. 在LR字符串中交换相邻字符

题目描述：

在一个由 ‘L’ , ‘R’ 和 ‘X’ 三个字符组成的字符串（例如”RXXLRXRXL”）中进行移动操作。

一次移动操作指用一个”LX”替换一个”XL”，或者用一个”XR”替换一个”RX”。

现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

示例 1：

输入: start = "RXXLRXRXL", end = "XRLXXRRLX"
输出: True
解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

提示：

• 1 <= len(start) = len(end) <= 10000。
• start和end中的字符串仅限于’L’, ‘R’和’X’。

---

解题分析及思路：

思路：

每次移动操作将 “XL” 替换成 “LX”，或将 “RX” 替换成 “XR”，等价于如下操作：

• 针对字符 ‘L’ 它在end的下标一定比start的下标要小，因为将 “XL” 替换成 “LX”，‘L’的下标一定是变小的
• 同理，针对字符 ‘R’ 它在end的下标一定比start的下标要大，因为将 “RX” 替换成 “XR”，‘R’的下标一定是变大的
• 因为字符 ‘L’ 和 ‘R’ 的位置不可以互换，所以，我们可以通过比较start和end中字符 ‘L’ 和 ‘R’ 的位置来判断是否可以通过移动操作将start转换成end。

所以，遍历start、end字符串，找到第一个不是 ‘X’ 的字符，然后比较start和end中字符 ‘L’ 和 ‘R’ 的位置，如果不满足上述条件，则返回false，否则继续遍历。

func canTransform(start string, end string) bool {
	var n, startIndex, endIndex = len(start), 0, 0
	for startIndex < n || endIndex < n {
		for startIndex < n && start[startIndex] == 'X' {
			startIndex++
		}
		for endIndex < n && end[endIndex] == 'X' {
			endIndex++
		}
		if startIndex == n || endIndex == n {
			return startIndex == endIndex
		}
		if start[startIndex] != end[endIndex] {
			return false
		}
		if start[startIndex] == 'L' && startIndex < endIndex {
			return false
		}
		if start[startIndex] == 'R' && startIndex > endIndex {
			return false
		}
		startIndex++
		endIndex++
	}
	return startIndex == endIndex
}

复杂度：

• 时间复杂度：O(N)，其中 N 是 start 的长度。
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.7 MB,击败了85.71% 的Go用户