You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:
'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.'_' 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.
Example 2:
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.length1 <= n <= 105start and target consist of the characters 'L', 'R', and '_'.In this approach, both start and target strings are reduced by removing the blank spaces ('_'). After that, we directly compare the remaining sequences of characters to check if they match. Each character's position is then validated based on the rules: 'L' can only move left, and 'R' can only move right. If these sequences not only match but also adhere to the movement rules, the transformation is possible.
This Python solution initially checks if both strings can become the same after removing all blanks. Then, it stores the indices of 'L' and 'R' in both strings and compares their positions to ensure all rules are respected: 'L' cannot move right, 'R' cannot move left. The solution returns True only if all conditions are satisfied.
JavaScript
Java
C#
C++
C
Time Complexity: O(n), where n is the length of the input strings, since we traverse through the list a fixed number of times.
Space Complexity: O(n) due to the extra lists created for positions of 'L' and 'R'.
This approach simulates the movement of 'L' and 'R' pieces while iterating through both strings simultaneously. It maintains cursors for both strings, moving them forward as each piece is appropriately moved according to the rules. 'L' must be moved only left, while 'R' needs space to go right, ensuring no rule violations exist.
This Python implementation uses two pointers, one for each string, skipping underscores, and comparing positions. It checks the position rules for 'L' and 'R'. The final condition ensures no unmatched characters exist. It’s efficient as it simply processes each character once.
JavaScript
Java
C#
C++
C
Time Complexity: O(n), because of the single pass through start and target strings.
Space Complexity: O(1), as no additional space proportional to the input is utilized.
| Approach | Complexity |
|---|---|
| Check Character Positions after Removing Blanks | Time Complexity: O(n), where n is the length of the input strings, since we traverse through the list a fixed number of times. |
| Simulate Piece Movement | Time Complexity: O(n), because of the single pass through start and target strings. |
Move Pieces to Obtain a String | Brute Force | Wrong | Optimal | Leetcode 2337 | codestorywithMIK • codestorywithMIK • 8,931 views views
Watch 9 more video solutions →Practice Move Pieces to Obtain a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor