不同的循环子字符串
难度:
标签:
题目描述
代码结果
运行时间: 538 ms, 内存: 16.8 MB
/*
* 题目思路:
* 同样的思路使用 Java Stream 来实现。
* 使用 Stream 对字符串进行过滤和收集。
*/
import java.util.stream.Collectors;
import java.util.HashSet;
import java.util.Set;
public class SolutionStream {
public int countDistinctSubstrings(String text) {
Set<String> seen = new HashSet<>();
int n = text.length();
return java.util.stream.IntStream.rangeClosed(2, n)
.filter(len -> len % 2 == 0)
.mapToObj(len -> java.util.stream.IntStream.range(0, n - len + 1)
.mapToObj(i -> text.substring(i, i + len))
.filter(substr -> substr.substring(0, len / 2).equals(substr.substring(len / 2)))
.collect(Collectors.toSet()))
.flatMap(Set::stream)
.collect(Collectors.toSet()).size();
}
}
解释
方法:
该题解的核心思路是利用哈希表来记录每个字符出现的所有位置,然后依此判断是否存在形如a+a的子字符串。具体实现中,遍历字符串的每个字符,利用一个字典res存储每个字符和其出现位置的列表。对于当前字符t和位置i,检查之前所有t出现的位置,判断在这些位置之间的字符串是否可以形成a+a。这是通过比较两个相邻位置间的字符串是否相同来完成的。如果相同,则将该字符串加入到结果集合ans中。最终,返回集合ans的大小,即不同的符合条件的子字符串数目。
时间复杂度:
O(n^3)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么可以通过比较两个相邻位置间的字符串来确定是否形成a+a的子字符串?
▷🦆
在实现中,为何使用集合(set)来存储符合条件的子字符串?是否有其他数据结构能达到同样的目的?
▷🦆
代码中的`if index + 1 >= i - index`条件是为了什么?这个条件帮助解决了什么潜在问题?
▷🦆
哈希表res存储每个字符出现的所有位置,这种方法在什么情况下效率最高,什么情况下可能效率较低?
▷