前言
持续更新了
正文
问题来源
本问题来自leetcode上的777题。
问题描述
在一个由 ‘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
示例 2:
输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
分析：
可以用双指针来解决这个问题，对于 i， j 两个指针，分别让他们指向 start 和 end，且保证 start[i] != ‘X’，end[j] != ‘X’。接下来开始移动指针，如果 start[i] != end[j]，则不满足 转换不变性，如果 start[i] == ‘L’ 且 i < j，则不满足 可到达性。
func canTransform(start string, end string) bool {
if len(start) != len(end) {
return false
}
n := len(start)
i, j := 0, 0
for i < n && j < n {
for i < n && start[i] == 'X' {
i++
}
for j < n && end[j] == 'X' {
j++
}
if (i >= n) && (j >= n) {
return true
} else if i < n && j < n {
if start[i] != end[j] || (start[i] == 'L' && i < j) || (start[i] == 'R' && i > j) {
fmt.Println(i, j)
return false
}
} else {
return false
}
i++
j++
}
for i < n && start[i] == 'X' {
i++
}
for j < n && end[j] == 'X' {
j++
}
if i == j {
return true
}
return false
}
总结：
勤思考。
结语
不管怎么样好好加油。
