2337. Move Pieces to Obtain a String LeetCode Solution
In this guide, you will get 2337. Move Pieces to Obtain a String LeetCode Solution with the best time and space complexity. The solution to Move Pieces to Obtain a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 a piece ‘R’ can move to the right only if there is a blank space directly to its right.
The character ‘_’ represents a blank space that can be occupied by any of the ‘L’ or ‘R’ pieces.
Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.
Example 1:
Input: start = “_L__R__R_”, target = “L______RR”
Output: true
Explanation: We can obtain the string target from start by doing the following moves:
– Move the first piece one step to the left, start becomes equal to “L___R__R_”.
– Move the last piece one step to the right, start becomes equal to “L___R___R”.
– Move the second piece three steps to the right, start becomes equal to “L______RR”.
Since it is possible to get the string target from start, we return true.
Input: start = “R_L_”, target = “__LR”
Output: false
Explanation: The ‘R’ piece in the string start can move one step to the right to obtain “_RL_”.
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.
Example 3:
Input: start = “_R”, target = “R_”
Output: false
Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.
Constraints:
n == start.length == target.length
1 <= n <= 105
start and target consist of the characters 'L', 'R', and '_'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2337. Move Pieces to Obtain a String LeetCode Solution in C++
class Solution {
public:
bool canChange(string start, string target) {
const int n = start.length();
int i = 0; // start's index
int j = 0; // target's index
while (i <= n && j <= n) {
while (i < n && start[i] == '_')
++i;
while (j < n && target[j] == '_')
++j;
if (i == n || j == n)
return i == n && j == n;
if (start[i] != target[j])
return false;
if (start[i] == 'R' && i > j)
return false;
if (start[i] == 'L' && i < j)
return false;
++i;
++j;
}
return true;
}
}; /* code provided by PROGIEZ */
2337. Move Pieces to Obtain a String LeetCode Solution in Java
class Solution {
public boolean canChange(String start, String target) {
final int n = start.length();
int i = 0; // start's index
int j = 0; // target's index
while (i <= n && j <= n) {
while (i < n && start.charAt(i) == '_')
++i;
while (j < n && target.charAt(j) == '_')
++j;
if (i == n || j == n)
return i == n && j == n;
if (start.charAt(i) != target.charAt(j))
return false;
if (start.charAt(i) == 'R' && i > j)
return false;
if (start.charAt(i) == 'L' && i < j)
return false;
++i;
++j;
}
return true;
}
} // code provided by PROGIEZ
2337. Move Pieces to Obtain a String LeetCode Solution in Python
class Solution:
def canChange(self, start: str, target: str) -> bool:
n = len(start)
i = 0 # start's index
j = 0 # target's index
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 or j == n:
return i == n and j == n
if start[i] != target[j]:
return False
if start[i] == 'R' and i > j:
return False
if start[i] == 'L' and i < j:
return False
i += 1
j += 1
return True # code by PROGIEZ
