Google
777 Swap Adjacent in LR String

1. Question

In a string composed of'L','R', and'X'characters, like"RXXLRXRXL", a move consists of either replacing one occurrence of"XL"with"LX", or replacing one occurrence of"RX"with"XR". Given the starting stringstartand the ending stringend, returnTrueif and only if there exists a sequence of moves to transform one string to the other.
Example:
1
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
2
3
Output: True
4
5
Explanation:
6
We can transform start to end following these steps:
7
RXXLRXRXL ->
8
XRXLRXRXL ->
9
XRLXRXRXL ->
10
XRLXXRRXL ->
11
XRLXXRRLX
Copied!
Note:
  1. 1.
    1 <= len(start) = len(end) <= 10000.
  2. 2.
    Both start and end will only consist of characters in{'L', 'R', 'X'}.

2. Implementation

(1) Two Pointers
1
class Solution {
2
public boolean canTransform(String start, String end) {
3
if (start.length() != end.length()) {
4
return false;
5
}
6
7
int countX1 = 0, countX2 = 0;
8
int index1 = 0, index2 = 0;
9
10
while (index1 < start.length() && index2 < end.length()) {
11
// Get the first non x character in start string, and count the number of X
12
while (index1 < start.length() && start.charAt(index1) == 'X') {
13
++countX1;
14
++index1;
15
}
16
17
// Get the first non x character in end string, and count the number of X
18
while (index2 < end.length() && end.charAt(index2) == 'X') {
19
++countX2;
20
++index2;
21
}
22
23
// Both strings get to the end, return true;
24
if (index1 == start.length() && index2 == end.length()) {
25
return true;
26
}
27
// One of the string is running out of character, return false;
28
else if (index1 == start.length() || index2 == end.length()) {
29
return false;
30
}
31
// If the first non x character are different, since L will only get to left, and R can only get to right,
32
// there is no way for start string to be transformed into end string
33
else if (start.charAt(index1) != end.charAt(index2)) {
34
return false;
35
}
36
// L can only get to left, if number of x in start is less than number of x in end string, it is impossible for e
37
// start string to be transformed into end string
38
else if (start.charAt(index1) == 'L' && countX1 < countX2) {
39
return false;
40
}
41
// R can only get tor right, if number of x in start is greater than the number of x in end string, it is impossible
42
// start string to be transformed into end string
43
else if (start.charAt(index1) == 'R' && countX1 > countX2) {
44
return false;
45
}
46
else {
47
++index1;
48
++index2;
49
}
50
}
51
return true;
52
}
53
}
Copied!

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)