grid47 Exploring patterns and algorithms
Aug 21, 2024
7 min read
Solution to LeetCode 777: Swap Adjacent in LR String Problem
You are given a string start and a string result composed of the characters ‘L’, ‘R’, and ‘X’. A move consists of either replacing an occurrence of ‘XL’ with ‘LX’, or replacing an occurrence of ‘RX’ with ‘XR’. Return true if it is possible to transform start into result by applying a sequence of these moves.
Problem
Approach
Steps
Complexity
Input: The input consists of two strings: start and result. Both strings are composed of characters 'L', 'R', and 'X'.
Example: Input: start = 'XRRXXLRX', result = 'XRRLXXRX'
Constraints:
• 1 <= start.length <= 10^4
• start.length == result.length
• Both strings consist only of the characters 'L', 'R', and 'X'.
Output: Return true if it is possible to transform start into result through a series of valid moves, otherwise return false.
Example: Output: true
Constraints:
• The output must be either true or false based on the possibility of transformation.
Goal: The goal is to check if a sequence of moves can transform the start string into the result string.
Steps:
• First, ensure that both the start and result strings contain the same number of 'L' and 'R' characters.
• Then, compare the positions of 'L' and 'R' in the start and result strings.
• Finally, verify that no illegal swaps (such as moving 'L' after 'R' in the wrong direction) are attempted.
Goal: The constraints ensure that both start and result strings have the same length, and the solution needs to handle strings of size up to 10^4 efficiently.
Steps:
• Both start and result strings are guaranteed to have the same length.
• Both strings only consist of characters 'L', 'R', and 'X'.
• The number of 'L' and 'R' in the start string must match the result string.
Assumptions:
• The input strings will be of equal length and consist only of 'L', 'R', and 'X'.
• Input: Example 1: Input: start = 'XRRXXLRX', result = 'XRRLXXRX'
• Explanation: The transformation is possible in one step: XRRXXLRX → XRRLXXRX.
• Input: Example 2: Input: start = 'LR', result = 'RL'
• Explanation: No sequence of moves can transform 'LR' to 'RL', so the result is false.
Approach: The approach is to simulate the moves by checking the positions of 'L' and 'R' in both the start and result strings. If any invalid moves are detected (such as moving 'L' after 'R' in the wrong direction), return false.
Observations:
• We need to check if the relative positions of 'L' and 'R' in the start string can be matched in the result string.
• By checking the relative positions and ensuring no invalid moves are attempted, we can determine if the transformation is possible.
Steps:
• Check if the number of 'L' and 'R' in both strings are equal.
• Simulate the moves by comparing the positions of 'L' and 'R'.
• Ensure no illegal swaps are performed during the transformation.
Empty Inputs:
• The input strings will always have at least one character.
Large Inputs:
• The solution should efficiently handle strings with up to 10^4 characters.
Special Values:
• If both the start and result strings are already the same, the answer should be true.
Constraints:
• Both strings will always consist of 'L', 'R', and 'X'.
boolcanTransform(string start, string end) {
int n = start.size();
string s1, s2;
for (int i =0; i < n; ++i)
if (start[i] !='X') s1 += start[i];
for (int i =0; i < n; ++i)
if (end[i] !='X') s2 += end[i];
if (s1 != s2) returnfalse;
int p1 =0, p2 =0;
while(p1 < start.size() && p2 < end.size()) {
while(p1 < start.size() && start[p1] =='X') p1++;
while(p2 < end.size() && end[p2] =='X') p2++;
if(p1 == start.size() && p2 == end.size()) returntrue;
if(p1 == start.size() || p2 == end.size()) returnfalse;
if(start[p1] != end[p2]) returnfalse;
if(start[p1] =='L'&& p2 > p1) returnfalse;
if(start[p1] =='R'&& p2 < p1) returnfalse;
p1++;
p2++;
}
returntrue;
}
1 : Function Definition
boolcanTransform(string start, string end) {
Define the function to check if one string can be transformed into another while following specific movement rules for 'L', 'R', and 'X'.
2 : Variable Initialization
int n = start.size();
Initialize 'n' to store the length of the 'start' string.
3 : Variable Declaration
string s1, s2;
Declare two strings 's1' and 's2' that will store characters from 'start' and 'end' respectively, excluding 'X' characters.
4 : Loop Start (start string)
for (int i =0; i < n; ++i)
Start a loop to iterate through the 'start' string.
5 : Character Filtering (start string)
if (start[i] !='X') s1 += start[i];
If the current character in 'start' is not 'X', append it to 's1'.
6 : Loop Start (end string)
for (int i =0; i < n; ++i)
Start a loop to iterate through the 'end' string.
7 : Character Filtering (end string)
if (end[i] !='X') s2 += end[i];
If the current character in 'end' is not 'X', append it to 's2'.
8 : String Comparison
if (s1 != s2) returnfalse;
If the filtered strings 's1' and 's2' are not the same, return false, as transformation is not possible.
9 : Pointer Initialization
int p1 =0, p2 =0;
Initialize two pointers 'p1' and 'p2' to traverse through the 'start' and 'end' strings.
10 : While Loop Start
while(p1 < start.size() && p2 < end.size()) {
Start a loop that continues as long as there are characters left in both 'start' and 'end'.
11 : Skip 'X' in start
while(p1 < start.size() && start[p1] =='X') p1++;
Move the pointer 'p1' forward while it points to 'X' characters in the 'start' string.
12 : Skip 'X' in end
while(p2 < end.size() && end[p2] =='X') p2++;
Move the pointer 'p2' forward while it points to 'X' characters in the 'end' string.
