diff options
-rw-r--r-- | move_pieces_obtain_string.c | 42 | ||||
-rw-r--r-- | move_pieces_obtain_string.py | 44 |
2 files changed, 86 insertions, 0 deletions
diff --git a/move_pieces_obtain_string.c b/move_pieces_obtain_string.c new file mode 100644 index 0000000..69020f6 --- /dev/null +++ b/move_pieces_obtain_string.c @@ -0,0 +1,42 @@ +// 2337. Move Pieces to Obtain a String +#include "leetcode.h" + +/* + * you are given two strings 'start' and 'target' both of length 'n'. each + * string consists only of the characters 'L', 'R', and '_' where the characters + * 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if + * there is a blank space directly to its left, and piece 'R' can move to the + * right only if there is a blank space directly to its right. return true if it + * is possible to obtain the string 'target' by moving the pieces of string + * 'start' any number of times. otherwise, return false. + */ + +bool canChange(char *start, char *target) { + int n = strlen(target), i = 0, j = 0; + while (i <= n && j <= n) { + while (i < n && target[i] == '_') + i++; + while (j < n && start[j] == '_') + j++; + if (i == n || j == n) + return i == n && j == n; + if (target[i] != start[j]) + return false; + if (target[i] == 'L') { + if (j < i) + return false; + } else if (i < j) + return false; + i++, j++; + } + return true; +} + +int main() { + char *s1 = "_L__R__R_", *t1 = "L______RR"; + char *s2 = "R_L_", *t2 = "__LR"; + char *s3 = "_R", *t3 = "R_"; + printf("%d\n", canChange(s1, t1)); // expect: 1 + printf("%d\n", canChange(s2, t2)); // expect: 0 + printf("%d\n", canChange(s3, t3)); // expect: 0 +} diff --git a/move_pieces_obtain_string.py b/move_pieces_obtain_string.py new file mode 100644 index 0000000..3412edd --- /dev/null +++ b/move_pieces_obtain_string.py @@ -0,0 +1,44 @@ +# 2337. Move Pieces to Obtain a String + +""" +you are given two strings 'start' and 'target' both of length 'n'. each +string consists only of the characters 'L', 'R', and '_' where the characters +'L' and 'R' represent pieces, where a piece 'L' can move to the left only if +there is a blank space directly to its left, and piece 'R' can move to the +right only if there is a blank space directly to its right. return true if it +is possible to obtain the string 'target' by moving the pieces of string +'start' any number of times. otherwise, return false. +""" + + +class Solution(object): + def canChange(self, start, target): + """ + :type start: str + :type target: str + :rtype: bool + """ + if start.replace("_", "") != target.replace("_", ""): + return False + n, i, j = len(start), 0, 0 + while i < n and j < n: + while i < n and start[i] == "_": + i += 1 + while j < n and target[j] == "_": + j += 1 + if ( + i < n + and j < n + and (start[i] == "L" and i < j or start[i] == "R" and i > j) + ): + return False + i += 1 + j += 1 + return True + + +if __name__ == "__main__": + obj = Solution() + print(obj.canChange(start="_L__R__R_", target="L______RR")) + print(obj.canChange(start="R_L_", target="__LR")) + print(obj.canChange(start="_R", target="R_")) |