题目简介：
在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。
示例 :
1
2
3
4
5
6
7
8
9
| 输入: start = "RXXLRXRXL", end = "XRLXXRRLX"
输出: True
解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
|
提示：
1 <= len(start) = len(end) <= 10000。start和end中的字符串仅限于'L', 'R'和'X'。
思路：
首先我们记录每一个L, R左侧X的数量，若两个字符串X数量不相等，则返回false。
由于L只能往左边移动，R只能往右边移动，因此我们只需找到start和end中对应位置的字符
- 若它们不是一个字符，则返回
false。
- 若它们都为
L，但start[i]左侧X的数量小于end[j]左侧X的数量，则返回false。
- 若它们都为
R，但start[i]左侧X的数量大于end[j]左侧X的数量，则返回false。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class Solution {
public:
bool canTransform(string start, string end) {
vector<int> dp(start.size(), 0);
vector<int> dp2(end.size(), 0);
for(int i = 0; i < start.size(); i++){
if(i == 0){
if(start[i] == 'X')
dp[i] = 1;
if(end[i] == 'X')
dp2[i] = 1;
}
else{
dp[i] = (start[i] == 'X') ? dp[i - 1] + 1 : dp[i - 1];
dp2[i] = (end[i] == 'X') ? dp2[i - 1] + 1 : dp2[i - 1];
}
}
if(dp[start.size() - 1] != dp2[end.size() - 1])
return false;
int i = 0, j = 0;
while(i < start.size() && j < end.size()){
while(start[i] == 'X')
i++;
while(end[j] == 'X')
j++;
if(start[i] != end[j])
return false;
if(start[i] == 'R' && dp[i] > dp2[j])
return false;
if(start[i] == 'L' && dp[i] < dp2[j])
return false;
i++;
j++;
}
return true;
}
};
|
