LeetCode 777. Swap Adjacent in LR String. Google Interview Question.

Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: true
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
Input: start = "LLR", end = "RRL"
Output: false
Input: start = "XLLR", end = "LXLX"
Output: false

Explanation

class Solution:
def canTransform(self, start: str, end: str) -> bool:
if len(start) != len(end): return False

# check L R orders are the same
if start.replace('X','') != end.replace('X', ''): return False

n = len(start)
Lstart = [i for i in range(n) if start[i] == 'L']
Lend = [i for i in range(n) if end[i] == 'L']

Rstart = [i for i in range(n) if start[i] == 'R']
Rend = [i for i in range(n) if end[i] == 'R']
# check L positions are correct
for i, j in zip(Lstart, Lend):
if i < j:
return False

# check R positions are correct
for i, j in zip(Rstart, Rend):
if i > j:
return False

return True

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store