[LeetCode] Move Pieces to Obtain a String

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 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
bool canChange(string A, string B) {
unordered_map<char,queue<int>> mp;
int n = A.length();
for(int i = 0; i < n; i++) {
mp[A[i]].push(i);
}
for(int i = 0; i < n; i++) {
int l,r,h;
l = mp['L'].empty() ? INT_MAX : mp['L'].front();
r = mp['R'].empty() ? INT_MAX : mp['R'].front();
h = mp['_'].empty() ? INT_MAX : mp['_'].front();
if(B[i] == 'L') {
if(l < r and l < h) {
mp['L'].pop();
} else if(r < l and r < h) {
return false;
} else {
if(l < r) mp['L'].pop();
else return false;
}
} else if(B[i] == 'R') {
if(r < l and r < h) mp['R'].pop();
else return false;
} else if(B[i] == '_') {
if(l < r and l < h) return false;

mp['_'].pop();
}
}
return true;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/07/10/PS/LeetCode/move-pieces-to-obtain-a-string/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.