leetcode
leetcode 1601 ~ 1650
统计距离最小的子串对个数

统计距离最小的子串对个数

难度:

标签:

题目描述

代码结果

运行时间: 92 ms, 内存: 17.3 MB


/*
题目思路:
1. 使用Java Stream API处理字符串。
2. 遍历字符串的所有子串。
3. 计算每个子串对之间的距离。
4. 找出距离最小的子串对。
5. 统计这些最小距离的子串对的个数。
*/

import java.util.stream.IntStream;
import java.util.stream.Stream;

public class SolutionStream {
    public long countMinDistanceSubstrings(String s) {
        int n = s.length();

        int minDistance = IntStream.range(0, n)
            .flatMap(i -> IntStream.range(i + 1, n)
            .map(j -> Math.abs(j - i)))
            .min()
            .orElse(Integer.MAX_VALUE);

        long count = IntStream.range(0, n)
            .flatMap(i -> IntStream.range(i + 1, n)
            .map(j -> Math.abs(j - i)))
            .filter(distance -> distance == minDistance)
            .count();

        return count;
    }

    public static void main(String[] args) {
        SolutionStream sol = new SolutionStream();
        String s = "abcde";
        System.out.println(sol.countMinDistanceSubstrings(s)); // 示例
    }
}

解释

方法:

该题解首先通过两个字典pre和post分别记录firstString中每个字符最早出现的位置和secondString中每个字符最后出现的位置。接着,它遍历这两个字典中的公共字符,计算每个字符在firstString和secondString中的位置差,并记录下最小的位置差minVal及其出现次数minCnt。最后,返回minVal对应的次数minCnt,即为最小距离子串对的个数。

时间复杂度:

O(n + m)

空间复杂度:

O(n + m)

代码细节讲解

🦆
为什么在记录firstString和secondString中字符的位置时选择使用字典而不是其他数据结构?
在这个算法中,字典用于快速查找和更新字符的位置信息。使用字典(或哈希表)可以在平均情况下以 O(1) 的时间复杂度进行访问和更新操作。这对于频繁的查询和更新操作是非常高效的。如果使用数组或列表,虽然可以通过索引快速访问,但查找特定字符的位置则需要 O(n) 的时间复杂度,这会增加算法的整体时间成本。
🦆
在计算最小位置差minVal时,如果firstString或secondString中的字符不存在于另一个字符串中,这种情况如何处理?
在这个算法中,只有当一个字符同时存在于 firstString 和 secondString 中时,才会计算位置差。这是通过在字典操作中使用集合的交集操作 pre.keys() & post.keys() 来实现的。如果一个字符只存在于其中一个字符串中,那么它不会出现在这个交集中,因此不会影响位置差的计算。
🦆
minVal初始化为inf,这在Python中代表什么意义,为什么选择它作为初始值?
在Python中,'inf' 代表无穷大。初始化 minVal 为 inf 是为了确保任何实际计算出的位置差都会小于这个初始值。这样,第一次比较时,任何实际的位置差都会替换掉 inf,从而开始有效地追踪最小的位置差。这是一种常用的技术,用来简化最小值的更新逻辑,避免设置一个具体的初始值可能导致的问题。
🦆
如何处理字符串中的特殊字符或重复字符,它们对算法的影响是什么?
对于特殊字符,只要它们在字符串中有定义的位置,该算法就像处理普通字符一样处理它们。对于重复字符,算法在 firstString 中记录每个字符第一次出现的位置,在 secondString 中记录每个字符最后一次出现的位置。这种处理方法确保了即使字符重复出现,算法也只关注对最小位置差计算最有影响的位置(即 firstString 中的最早位置和 secondString 中的最晚位置)。

相关问题