leetcode
leetcode 1051 ~ 1100
不同的循环子字符串

不同的循环子字符串

难度:

标签:

题目描述

代码结果

运行时间: 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的子字符串?
在给定的算法中,我们寻找形式为a+a的字符串,这意味着字符串由两个相同的部分a组成。通过记录每个字符出现的所有位置,我们可以找到所有可能的相同字符对的位置组合。对于字符t的任意两个相邻出现位置index和i(index < i),如果在index和i之间的字符串长度与从index到i的长度相等且内容相同,那么这部分字符串就是形式为a+a。因此,通过比较这两个相邻位置间的字符串是否相同,可以有效地判断是否形成了所需的子字符串结构。
🦆
在实现中,为何使用集合(set)来存储符合条件的子字符串?是否有其他数据结构能达到同样的目的?
使用集合(set)来存储符合条件的子字符串的主要目的是利用集合的自动去重特性,这可以有效地防止同一个子字符串被多次计数。集合在这种情况下提供了简单且高效的去重方法。尽管其他数据结构例如列表(list)也可以用来存储这些子字符串,但它们则需要额外的操作来保证元素的唯一性,如使用循环来检查重复或者在添加前进行查找,这会增加时间复杂性。另一种选择是哈希表(如Python中的字典),它同样可以达到去重的目的,但对于本问题而言,集合更为直接和高效。
🦆
代码中的`if index + 1 >= i - index`条件是为了什么?这个条件帮助解决了什么潜在问题?
这个条件确保了在比较两个相邻位置间的字符串内容前,后一个位置i与前一个位置index之间有足够的字符来构成一个可能的a+a结构。具体来说,`i - index`是两个相邻位置之间的距离,而`index + 1 >= i - index`确保了从index开始的字符串长度至少与index到i之间的距离相等,这是形成a+a结构的基本要求。如果没有这个条件,可能会导致字符串比较时越界,或者比较不等长的字符串,从而造成逻辑错误。
🦆
哈希表res存储每个字符出现的所有位置,这种方法在什么情况下效率最高,什么情况下可能效率较低?
哈希表res存储每个字符出现的所有位置,在字符分布较均匀或字符串较短时效率较高,因为这样可以较快地访问和更新每个字符的位置列表。当字符串较长且某些字符非常频繁地出现时,效率可能较低。在这种情况下,每个字符的位置列表可能变得非常长,导致每次更新位置列表和检查可能的a+a结构时耗时增加。此外,如果字符很少重复,那么哈希表的优势不明显,因为大部分位置列表都非常短。

相关问题