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

难度: Medium

Submission

运行时间: 92 ms

内存: 17.3 MB

class Solution:
    def countQuadruples(self, firstString: str, secondString: str) -> int:
        pre, post = {}, {}
        
        for i, x in enumerate(firstString):
            if x in pre: continue
            pre[x] = i
        
        for j, y in enumerate(secondString):
            post[y] = j
        
        minVal, minCnt = inf, 0
        for c in pre.keys() & post.keys():
            if (v := pre[c] - post[c]) < minVal:
                minVal, minCnt = v, 1
            elif v == minVal:
                minCnt += 1
        return minCnt

Explain

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

时间复杂度: O(n + m)

空间复杂度: O(n + m)

class Solution:
    def countQuadruples(self, firstString: str, secondString: str) -> int:
        pre, post = {}, {}
        
        # 记录firstString中每个字符最早出现的位置
        for i, x in enumerate(firstString):
            if x in pre: continue
            pre[x] = i
        
        # 记录secondString中每个字符最后出现的位置
        for j, y in enumerate(secondString):
            post[y] = j
        
        minVal, minCnt = inf, 0
        # 遍历公共字符，计算位置差
        for c in pre.keys() & post.keys():
            v = pre[c] - post[c]
            if v < minVal:
                minVal, minCnt = v, 1
            elif v == minVal:
                minCnt += 1
        return minCnt

Explore

在这个算法中，字典用于快速查找和更新字符的位置信息。使用字典（或哈希表）可以在平均情况下以 O(1) 的时间复杂度进行访问和更新操作。这对于频繁的查询和更新操作是非常高效的。如果使用数组或列表，虽然可以通过索引快速访问，但查找特定字符的位置则需要 O(n) 的时间复杂度，这会增加算法的整体时间成本。

在这个算法中，只有当一个字符同时存在于 firstString 和 secondString 中时，才会计算位置差。这是通过在字典操作中使用集合的交集操作 pre.keys() & post.keys() 来实现的。如果一个字符只存在于其中一个字符串中，那么它不会出现在这个交集中，因此不会影响位置差的计算。

在Python中，'inf' 代表无穷大。初始化 minVal 为 inf 是为了确保任何实际计算出的位置差都会小于这个初始值。这样，第一次比较时，任何实际的位置差都会替换掉 inf，从而开始有效地追踪最小的位置差。这是一种常用的技术，用来简化最小值的更新逻辑，避免设置一个具体的初始值可能导致的问题。

对于特殊字符，只要它们在字符串中有定义的位置，该算法就像处理普通字符一样处理它们。对于重复字符，算法在 firstString 中记录每个字符第一次出现的位置，在 secondString 中记录每个字符最后一次出现的位置。这种处理方法确保了即使字符重复出现，算法也只关注对最小位置差计算最有影响的位置（即 firstString 中的最早位置和 secondString 中的最晚位置）。