diff options
author | Jack Sangdahl <[email protected]> | 2024-09-03 12:36:33 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-03 12:36:33 -0600 |
commit | 798aeafad06ab1e7dde6d4d5050a49c7fcb5eb1c (patch) | |
tree | 7504059333e94317f8e4260c43825c7f01bd3fda | |
parent | 8f4686e3871ac66ce00447f429cff45c8032ffa4 (diff) | |
download | leetcode-798aeafad06ab1e7dde6d4d5050a49c7fcb5eb1c.tar.gz leetcode-798aeafad06ab1e7dde6d4d5050a49c7fcb5eb1c.zip |
777. swap adjacent in lr string
-rw-r--r-- | swap_adjacent_lr_string.c | 42 | ||||
-rw-r--r-- | swap_adjacent_lr_string.py | 38 |
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")) |