# 777. Swap Adjacent in LR String¶

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: bool canTransform(string start, string end) { if (removeX(start) != removeX(end)) return false; int i = 0; // start's index int j = 0; // end's index while (i < start.length() && j < end.length()) { while (i < start.length() && start[i] == 'X') ++i; while (j < end.length() && end[j] == 'X') ++j; if (i == start.length() && j == end.length()) return true; if (i == start.length() || j == end.length()) return false; // L can only move to left. if (start[i] == 'L' && i < j) return false; // R can only move to right. if (start[i] == 'R' && i > j) return false; ++i; ++j; } return true; } private: string removeX(const string& s) { string t = s; t.erase(remove(t.begin(), t.end(), 'X'), t.end()); return t; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public boolean canTransform(String start, String end) { if (!start.replace("X", "").equals(end.replace("X", ""))) return false; int i = 0; // start's index int j = 0; // end's index while (i < start.length() && j < end.length()) { while (i < start.length() && start.charAt(i) == 'X') ++i; while (j < end.length() && end.charAt(j) == 'X') ++j; if (i == start.length() && j == end.length()) return true; if (i == start.length() || j == end.length()) return false; // L can only move to left. if (start.charAt(i) == 'L' && i < j) return false; // R can only move to right. if (start.charAt(i) == 'R' && i > j) return false; ++i; ++j; } return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution: def canTransform(self, start: str, end: str) -> bool: if start.replace('X', '') != end.replace('X', ''): return False i = 0 # start's index j = 0 # end's index while i < len(start) and j < len(end): while i < len(start) and start[i] == 'X': i += 1 while j < len(end) and end[j] == 'X': j += 1 if i == len(start) and j == len(end): return True if i == len(start) or j == len(end): return False # L can only move to left. if start[i] == 'L' and i < j: return False # R can only move to right. if start[i] == 'R' and i > j: return False i += 1 j += 1 return True