移动片段得到字符串
难度:
标签:
题目描述
代码结果
运行时间: 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`?
▷🦆
在处理'R'字符的过程中,为什么遇到起始位置有额外的'R'时,需要检查`lc`是否为0?`lc`与处理'R'的逻辑有什么联系?
▷🦆
题解中提到,如果`lc`或`rc`计数器变为负数,则返回`false`。能否具体解释一下为什么负数的计数器值会导致返回`false`?
▷