777. Swap Adjacent in LR String

Problem Link

Description

---

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 result, return True if and only if there exists a sequence of moves to transform start to result.

 

Example 1:

Input: start = "RXXLRXRXL", result = "XRLXXRRLX"
Output: true
Explanation: We can transform start to result following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Example 2:

Input: start = "X", result = "L"
Output: false

 

Constraints:

• 1 <= start.length <= 104
• start.length == result.length
• Both start and result will only consist of characters in 'L', 'R', and 'X'.

Solution

---

Python3

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        if start == end: return True
        
        A = [(i, x) for i, x in enumerate(start) if x != "X"]
        B = [(i, x) for i, x in enumerate(end) if x != "X"]
        
        if len(A) != len(B): return False
        
        for (i, a), (j, b) in zip(A, B):
            if a != b: return False
            
            if a == "L":
                if i < j: return False
            else:
                if i > j: return False
        
        return True