Algorithm
Problem Name: 777. Swap Adjacent in LR String
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 1:
Input: start = "RXXLRXRXL", end = "XRLXXRRLX" Output: true Explanation: We can transform start to end following these steps: RXXLRXRXL -> XRXLRXRXL -> XRLXRXRXL -> XRLXXRRXL -> XRLXXRRLX
Example 2:
Input: start = "X", end = "L" Output: false
Constraints:
1 <= start.length <= 104start.length == end.length- Both
startandendwill only consist of characters in'L','R', and'X'.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool canTransform(char * start, char * end){
int i, j;
i = j = 0;
while (start[i] && end[i]) {
while (start[i] == 'X') i ++;
while (end[j] == 'X') j ++;
if (start[i] == 0 && end[j] == 0) return true;
if (start[i] == 0 || end[j] == 0) return false;
if (start[i] != end[j] ||
(start[i] == 'L' && i < j) ||
(start[i] == 'R' && i > j)) return false;
i ++; j ++;
}
return true;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool canTransform(string start, string end) {
int n = start.size();
string a, b;
vector<int>posA, posB;
for (int i = 0; i < n; ++i) {
if (start[i] != 'X') {
a.push_back(start[i]);
posA.push_back(i);
}
if (end[i] != 'X') {
b.push_back(end[i]);
posB.push_back(i);
}
}
if (a.size() != b.size()) {
return false;
}
for (int i = 0; i < a.size(); ++i) {
if (a[i] != b[i] || (a[i] == 'L' && posA[i] < posB[i] || a[i] == 'R' && posA[i] > posB[i])) {
return false;
}
}
return true;
}
};
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const canTransform = function(start, end) {
let r = 0, l = 0;
for (let i = 0; i < start.length; i++){
if (start.charAt(i) === 'R'){ r++; l = 0;}
if (end.charAt(i) === 'R') { r--; l = 0;}
if (end.charAt(i) === 'L') { l++; r = 0;}
if (start.charAt(i) === 'L') { l--; r = 0;}
if (l < 0 || r < 0) return false;
}
if (l != 0 || r != 0) return false;
return true;
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def canTransform(self, start, end):
s, e = collections.defaultdict(list), collections.defaultdict(list)
newS, newE = [c for c in start if c != "X"], [c for c in end if c != "X"]
for i in range(len(start)):
if start[i] != "X":
s[start[i]].append(i)
if end[i] != "X":
e[end[i]].append(i)
if newS == newE and len(s["L"]) == len(e["L"]) and len(s["R"]) == len(e["R"]):
if all(s["R"][i] <= e["R"][i] for i in range(len(s["R"]))) and all(s["L"][i] >= e["L"][i] for i in range(len(s["L"]))):
return True
return False
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0777_SwapAdjacentInLRString
{
public bool CanTransform(string start, string end)
{
var N = start.Length;
var startIndex = -1;
var endIndex = -1;
while (++startIndex < N && ++endIndex < N)
{
while (startIndex < N && start[startIndex] == 'X') startIndex++;
while (endIndex < N && end[endIndex] == 'X') endIndex++;
if ((startIndex == N && endIndex < N) || (startIndex < N && endIndex == N))
return false;
if (startIndex < N && endIndex < N)
if (start[startIndex] != end[endIndex] || (start[startIndex] == 'L' && startIndex < endIndex) || (start[startIndex] == 'R' && startIndex > endIndex))
return false;
}
return true;
}
}
}
Input
Output