Formatted question description: https://leetcode.ca/all/777.html
777. Swap Adjacent in LR String (Medium)
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 string start
and the ending string end
, return True
if and only if there exists a sequence of moves to transform one string to the other.
Example:
Input: start = "RXXLRXRXL", end = "XRLXXRRLX" Output: True Explanation: We can transform start to end following these steps: RXXLRXRXL -> XRXLRXRXL -> XRLXRXRXL -> XRLXXRRXL -> XRLXXRRLX
Note:
1 <= len(start) = len(end) <= 10000
.- Both start and end will only consist of characters in
{'L', 'R', 'X'}
.
Companies:
Google
Related Topics:
Brainteaser
Solution 1.
// OJ: https://leetcode.com/problems/swap-adjacent-in-lr-string/
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool canTransform(string start, string end) {
int N = start.size();
string a = start, b = end;
a.erase(remove(a.begin(), a.end(), 'X'), a.end());
b.erase(remove(b.begin(), b.end(), 'X'), b.end());
if (a != b) return false;
for (int i = 0, j = 0; i < N; ++i) {
if (start[i] == 'L') {
while (end[j] != 'L') ++j;
if (i < j++) return false;
}
}
for (int i = 0, j = 0; i < N; ++i) {
if (start[i] == 'R') {
while (end[j] != 'R') ++j;
if (i > j++) return false;
}
}
return true;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/swap-adjacent-in-lr-string/
// Time: O(N)
// Space: O(1)
class Solution {
public:
bool canTransform(string start, string end) {
int i = 0, j = 0, N = start.size();
for (; i < N && j < N; ++i, ++j) {
while (i < N && start[i] == 'X') ++i;
while (j < N && end[j] == 'X') ++j;
if ((i < N) ^ (j < N)) return false;
if (i < N && j < N) {
if (start[i] != end[j]
|| (start[i] == 'L' && i < j)
|| (start[i] == 'R' && i > j)) return false;
}
}
return true;
}
};
Java
class Solution {
public boolean canTransform(String start, String end) {
if (start == null || end == null || start.length() != end.length())
return false;
List<Integer> indices1 = getLRIndices(start);
List<Integer> indices2 = getLRIndices(end);
if (indices1.size() != indices2.size())
return false;
int size = indices1.size();
for (int i = 0; i < size; i++) {
int index1 = indices1.get(i), index2 = indices2.get(i);
if (index1 > 0 && index2 < 0 || index1 < 0 && index2 > 0 || index1 > index2)
return false;
}
return true;
}
public List<Integer> getLRIndices(String str) {
List<Integer> indices = new ArrayList<Integer>();
int length = str.length();
for (int i = 0; i < length; i++) {
char c = str.charAt(i);
if (c == 'L')
indices.add(-i - 1);
else if (c == 'R')
indices.add(i + 1);
}
return indices;
}
}