leetcode
leetcode 651 ~ 700
在LR字符串中交换相邻字符

在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',而不能继续跳过?
在算法中,'X' 视为可以通过忽略的空位,而 'L' 和 'R' 是有明确移动限制的字符。'L' 只能向左移动,'R' 只能向右移动。因此,遇到 'L' 或 'R' 时需要停止跳过 'X' 是为了检查这两个字符是否能在对应的位置上匹配或是否能通过合法的移动达到目标位置。如果继续跳过,我们可能会错过 'L' 和 'R' 之间的相对位置关系,这是判断转换是否可能的关键。
🦆
当指针i和j在字符串中的位置不相等时,为什么可以直接判断'L'只能向左移,而'R'只能向右移?这种判断依据是什么?
这种判断依据是 'L' 和 'R' 的移动规则。根据题目设定,'L' 只能向左移动(即向字符串的起始方向移动),而 'R' 只能向右移动(即向字符串的结束方向移动)。因此,如果在 start 字符串中 'L' 的位置在 end 字符串中的对应 'L' 的位置的右边,表示这个 'L' 在 end 中已经向左移动了;反之,如果 'R' 在 start 中的位置比在 end 中的位置靠左,表示这个 'R' 在 end 中已经向右移动了。这是按照它们各自的移动规则进行判断的逻辑结果。
🦆
在题解中,如何确保在指针跳过'X'后,两个字符串中的非'X'字符完全一致?是否有可能存在漏检的情况?
题解中通过双指针技术确保两个字符串中的非 'X' 字符完全一致。每次跳过 'X' 后,比较两个指针所指向的字符。如果这两个字符不同,则直接返回 False,这保证了只有当两个字符串中相同位置的非 'X' 字符相同时,算法才继续执行。如果某个指针到达字符串末尾而另一个没有,或者两个指针所指的非 'X' 字符不一致,都会被检测出来,因此不存在漏检的情况。
🦆
在循环结束后,题解中直接返回了i == j的结果,这种方法是否完全足够保证start可以通过规定的移动操作转换成end?
这种方法足够保证 start 可以通过规定的移动操作转换成 end。在循环中,已经确保了所有非 'X' 字符都能在合法的位置匹配,且字符间的相对位置满足移动规则。循环结束时,返回 i == j 的结果确保两个指针都同时达到各自字符串的末尾,这意味着除了 'X' 外,所有字符都已正确匹配,且没有多余的非 'X' 字符在任一字符串中。因此,这足以证明一个字符串可以通过规定的操作转换成另一个字符串。

相关问题