leetcode
leetcode 2001 ~ 2050
移动片段得到字符串

移动片段得到字符串

难度:

标签:

题目描述

代码结果

运行时间: 112 ms, 内存: 17.2 MB


/*
 * 思路:
 * 1. 使用Java Stream对字符串进行处理。
 * 2. 通过filter跳过下划线并将字符与其索引绑定。
 * 3. 使用allMatch来检查每个字符的位置移动是否合法。
 */
import java.util.stream.IntStream;

public class Solution {
    public boolean canTransform(String start, String target) {
        // 去除下划线后,两个字符串应当相等
        if (!start.replace("_", "").equals(target.replace("_", ""))) {
            return false;
        }

        int[] startIndexes = IntStream.range(0, start.length())
                                       .filter(i -> start.charAt(i) != '_')
                                       .toArray();
        int[] targetIndexes = IntStream.range(0, target.length())
                                        .filter(i -> target.charAt(i) != '_')
                                        .toArray();

        return IntStream.range(0, startIndexes.length)
                        .allMatch(i -> (start.charAt(startIndexes[i]) == target.charAt(targetIndexes[i]) &&
                                       (start.charAt(startIndexes[i]) != 'L' || startIndexes[i] >= targetIndexes[i]) &&
                                       (start.charAt(startIndexes[i]) != 'R' || startIndexes[i] <= targetIndexes[i])));
    }
}

解释

方法:

此题解首先检查`start`和`target`字符串中'L'和'R'的数量是否相等,如果不相等,则直接返回`false`,因为无法通过移动字符来平衡数量不同的片段。接着,使用两个计数器`lc`和`rc`分别跟踪'L'和'R'的位置偏差。遍历`start`和`target`字符串的每个字符,同时比较两者的字符。如果目标位置`t`需要一个'L',则增加`lc`;如果起始位置`s`有一个额外的'L',则减少`lc`。如果`lc`变为负数,表示在`target`中,'L'的位置在`start`之前,这是不可能的,因为'L'只能向左移动。类似的逻辑应用于'R'字符,但是注意`rc`的处理方式与`lc`相反,因为'R'只能向右移动。如果在任何时刻,`lc`和`rc`计数器的状态违反了移动规则,就返回`false`。如果整个过程中没有违规,最后返回`true`。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在遍历字符串时,如果`t`是'L'而`s`不是,只增加`lc`计数器而不是立即返回`false`?
在遍历字符串的过程中,如果在`target`中的位置`t`需要一个'L'而在`start`中的相应位置`s`不是'L',此时只增加`lc`计数器而不立即返回`false`是因为我们正在统计`target`中需要移动到的'L'字符数量。只有当`lc`计数器变为负数时,即出现在`start`中没有足够的'L'字符可以移动到`target`相应位置时,才返回`false`。这种延迟判断的方式允许我们在整个字符串遍历结束前,保留对字符位置匹配的灵活处理。
🦆
在处理'R'字符的过程中,为什么遇到起始位置有额外的'R'时,需要检查`lc`是否为0?`lc`与处理'R'的逻辑有什么联系?
在处理'R'字符的过程中,遇到起始位置有额外的'R'时需要检查`lc`是否为0,是因为`lc`计数器代表`L`字符的位置偏差。如果`lc`不为0,意味着在当前`R`字符的位置之前,存在未匹配或未正确放置的`L`字符,由于`L`只能向左移动,如果此时移动`R`字符(只能向右移动),可能会导致`L`和`R`的路径冲突或位置错误。因此,只有当所有`L`字符都已正确处理(即`lc`为0),才能安全地处理`R`字符。
🦆
题解中提到,如果`lc`或`rc`计数器变为负数,则返回`false`。能否具体解释一下为什么负数的计数器值会导致返回`false`?
在此算法中,`lc`和`rc`计数器分别跟踪`L`和`R`字符在`start`和`target`中的位置偏差。如果在任意时刻`lc`或`rc`变为负数,这表示在`target`字符串中,`L`或`R`字符出现的位置在`start`中没有足够的字符可以对应移动过去,即`target`要求的位置无法通过合法的移动得到。例如,`lc`变负意味着`target`中需要的`L`字符在`start`中没有足够的对应字符可以左移满足位置要求,因此违反了题目的移动规则,需要返回`false`。

相关问题