在LR字符串中交换相邻字符
难度:
标签:
题目描述
代码结果
运行时间: 33 ms, 内存: 16.1 MB
/*
题目思路:
1. 使用流API处理start和end字符串。
2. 使用过滤器忽略'X'字符,仅保留'L'和'R'。
3. 通过比较start和end中'L'和'R'的位置,确保符合题意的移动规则。
4. 如果条件满足,则返回true,否则返回false。
*/
import java.util.stream.Collectors;
public class Solution {
public boolean canTransform(String start, String end) {
if (start.length() != end.length()) return false;
String s = start.replaceAll("X", "");
String e = end.replaceAll("X", "");
if (!s.equals(e)) return false;
int n = start.length();
for (int i = 0, j = 0; i < n; i++) {
if (start.charAt(i) == 'X') continue;
while (end.charAt(j) == 'X') j++;
if (start.charAt(i) == 'L' && i < j) return false;
if (start.charAt(i) == 'R' && i > j) return false;
j++;
}
return true;
}
}
解释
方法:
这个题解的思路是使用双指针 i 和 j 分别在 start 和 end 字符串上移动。当指针所指的字符为 'X' 时,指针就一直向右移动,直到遇到 'L' 或 'R'。然后比较两个指针所指的字符是否相同,如果不同则返回 False。接着判断对于 'L' 和 'R' 的相对位置关系,'L' 只能向左移动,'R' 只能向右移动,如果位置关系不满足则返回 False。最后当任一指针达到字符串尾部时,判断两个指针是否同时到达尾部,如果不是则返回 False,否则返回 True。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在处理字符时,需要在遇到'L'或'R'时停止跳过'X',而不能继续跳过?
▷🦆
当指针i和j在字符串中的位置不相等时,为什么可以直接判断'L'只能向左移,而'R'只能向右移?这种判断依据是什么?
▷🦆
在题解中,如何确保在指针跳过'X'后,两个字符串中的非'X'字符完全一致?是否有可能存在漏检的情况?
▷🦆
在循环结束后,题解中直接返回了i == j的结果,这种方法是否完全足够保证start可以通过规定的移动操作转换成end?
▷