题目链接:https://leetcode.cn/problems/swap-adjacent-in-lr-string/description/
题目大意:给两个字符串start, end
,只包含XLR
三种字符。可以进行一次操作将XL
转换成LX
或者将RX
转换为XR
,返回是否存在方法使得start
能转换成end
思路:操作中可以看出,这只不过是让L和X或R和X交换位置而已,L、R的相对位置不会变。因此先把所有X去掉,看看只剩下LR的两个字符串是否一致。不一致就返回false
我原本以为这就到头了,但没想到还没过,看了题解才发现,这个交换中,L
只能左移,R
只能右移,因此还要对比一下start
和end
中,相对位置对应的每个L和R,是否满足【L
只能左移,R
只能右移】这个条件。这个步骤用双指针完成即可。
完整代码
class Solution {
public:
bool canTransform(string start, string end) {
string s1, s2;
for (auto c : start) {
if (c != 'X')
s1.push_back(c);
}
for (auto c : end) {
if (c != 'X')
s2.push_back(c);
}
if (s1 != s2)
return false;
int i = 0, j = 0;
while (i < start.size()) {
if (start[i] == 'X') {
i++;
continue;
}
while (j < end.size() && end[j] != start[i])
j++;
if (start[i] == 'R' && i > j)
return false;
if (start[i] == 'L' && i < j)
return false;
i++;
j++;
}
return true;
}
};