aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-03 12:36:33 -0600
committerJack Sangdahl <[email protected]>2024-09-03 12:36:33 -0600
commit798aeafad06ab1e7dde6d4d5050a49c7fcb5eb1c (patch)
tree7504059333e94317f8e4260c43825c7f01bd3fda
parent8f4686e3871ac66ce00447f429cff45c8032ffa4 (diff)
downloadleetcode-798aeafad06ab1e7dde6d4d5050a49c7fcb5eb1c.tar.gz
leetcode-798aeafad06ab1e7dde6d4d5050a49c7fcb5eb1c.zip
777. swap adjacent in lr string
-rw-r--r--swap_adjacent_lr_string.c42
-rw-r--r--swap_adjacent_lr_string.py38
2 files changed, 80 insertions, 0 deletions
diff --git a/swap_adjacent_lr_string.c b/swap_adjacent_lr_string.c
new file mode 100644
index 0000000..c7bbac9
--- /dev/null
+++ b/swap_adjacent_lr_string.c
@@ -0,0 +1,42 @@
+// 777. Swap Adjacent in LR String
+#include "leetcode.h"
+
+/*
+ * 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 'start' to 'end'
+ */
+
+bool canTransform(char *start, char *end) {
+ int c1 = 0, c2 = 0, i = 0, j = 0, n = strlen(start);
+ for (i = 0; i < n; i++) {
+ if (start[i] == 'X')
+ c1++;
+ if (end[i] == 'X')
+ c2++;
+ }
+ if (c1 != c2)
+ return false;
+ i = j = 0;
+ while (i < n && j < n) {
+ if (start[i] == 'X')
+ i++;
+ else if (end[j] == 'X')
+ j++;
+ else {
+ if ((start[i] != end[j]) || (start[i] == 'L' && i < j) ||
+ start[i] == 'R' && i > j)
+ return false;
+ i++, j++;
+ }
+ }
+ return true;
+}
+
+int main() {
+ char *s1 = "RXXLRXRXL", *e1 = "XRLXXRRLX", *s2 = "X", *e2 = "L";
+ printf("%d\n", canTransform(s1, e1)); // expect: 1
+ printf("%d\n", canTransform(s2, e2)); // expect: 0
+}
diff --git a/swap_adjacent_lr_string.py b/swap_adjacent_lr_string.py
new file mode 100644
index 0000000..e0ab186
--- /dev/null
+++ b/swap_adjacent_lr_string.py
@@ -0,0 +1,38 @@
+# 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 'start' to 'end'
+"""
+
+
+class Solution(object):
+ def canTransform(self, start, end):
+ """
+ :type start: str
+ :type end: str
+ :rtype: bool
+ """
+ if start.replace("X", "") != end.replace("X", ""):
+ return False
+ n = len(start)
+ l_start = [i for i in range(n) if start[i] == "L"]
+ l_end = [i for i in range(n) if end[i] == "L"]
+ r_start = [i for i in range(n) if start[i] == "R"]
+ r_end = [i for i in range(n) if end[i] == "R"]
+ for i, j in zip(l_start, l_end):
+ if i < j:
+ return False
+ for i, j in zip(r_start, r_end):
+ if i > j:
+ return False
+ return True
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.canTransform(start="RXXLRXRXL", end="XRLXXRRLX"))
+ print(obj.canTransform(start="X", end="L"))