统计前后缀下标对 II

标签: 字典树 数组 字符串 字符串匹配 哈希函数 滚动哈希

难度: Hard

给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

  • 当 str1 同时是 str2 的前缀（prefix）和后缀（suffix）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

示例 1：

输入：words = ["a","aba","ababa","aa"]
输出：4
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("a", "aba") 为 true 。
i = 0 且 j = 2 ，因为 isPrefixAndSuffix("a", "ababa") 为 true 。
i = 0 且 j = 3 ，因为 isPrefixAndSuffix("a", "aa") 为 true 。
i = 1 且 j = 2 ，因为 isPrefixAndSuffix("aba", "ababa") 为 true 。
因此，答案是 4 。

示例 2：

输入：words = ["pa","papa","ma","mama"]
输出：2
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("pa", "papa") 为 true 。
i = 2 且 j = 3 ，因为 isPrefixAndSuffix("ma", "mama") 为 true 。
因此，答案是 2 。

示例 3：

输入：words = ["abab","ab"]
输出：0
解释：在本示例中，唯一有效的下标对是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix("abab", "ab") 为 false 。
因此，答案是 0 。

提示：

  • 1 <= words.length <= 105
  • 1 <= words[i].length <= 105
  • words[i] 仅由小写英文字母组成。
  • 所有 words[i] 的长度之和不超过 5 * 105 。

Submission

运行时间: 159 ms

内存: 32.3 MB

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        n = len(words)
        if n == 0:
            return 0
        s2c = {words[-1] : 1}
        resn = 0
        for i in range(n-2, -1, -1):
            n1 = len(words[i])
            for s, c in s2c.items():
                if words[i] == s[:n1] and words[i] == s[-n1:]:
                    resn += c
            s2c[words[i]] = s2c.get(words[i], 0) + 1
        return resn

Explain

此题解采用了逆序遍历与哈希表的结合来优化查询和统计过程。首先，从数组的尾部开始遍历，使用哈希表s2c来记录遍历过的每个字符串及其出现次数。对于每个字符串words[i]，检查它是否为已记录在哈希表中的每个字符串的前缀和后缀。如果是，则累加对应字符串的计数到结果中。此方法避免了重复的字符串比较，利用哈希表快速地检索和更新字符串的出现次数。

时间复杂度: O(n^2 * l)

空间复杂度: O(n * l)

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        n = len(words)
        if n == 0:
            return 0
        # 哈希表存储每个字符串及其计数
        s2c = {words[-1] : 1}
        resn = 0
        # 从后向前遍历words数组
        for i in range(n-2, -1, -1):
            n1 = len(words[i])
            # 检查当前字符串是否为之前任一字符串的前后缀
            for s, c in s2c.items():
                if words[i] == s[:n1] and words[i] == s[-n1:]:
                    resn += c
            # 更新当前字符串的计数
            s2c[words[i]] = s2c.get(words[i], 0) + 1
        return resn

Explore

从数组的尾部向前遍历可以有效地利用哈希表记录已经遍历过的字符串及其出现次数，这样在遍历到每一个新字符串时，可以直接使用哈希表检查该字符串是否为任一已遍历字符串的前后缀。如果从数组头部开始遍历，每次遇到新字符串都需要向后检查所有未遍历的字符串，这将导致大量的重复比较和计算。逆序遍历让每个字符串在进入哈希表前先作为前缀和后缀候选，从而减少了计算量并提高了效率。

哈希表s2c在算法中扮演了关键的数据记录角色。它记录每一个已遍历字符串及其出现次数，使得在遍历到新的字符串时，可以直接利用哈希表来快速检查这个新字符串是否为任何已记录字符串的前缀或后缀。这种方法避免了对每个新字符串进行大量的字符串比较，从而显著减少了计算量。此外，使用哈希表还可以快速更新和查询字符串的计数，进一步提高算法的执行效率。

在更新哈希表s2c时，使用get方法可以方便地返回指定键的值，如果键不存在，则返回一个默认值，通常是0。这样可以在一行代码内完成查询和默认值处理，简化了代码并减少了错误的可能性。使用get方法更新哈希表不仅保证了代码的简洁性，还保持了高效性，因为它避免了先检查键是否存在再进行赋值的多步骤操作。这种方式确保了算法的正确性和高效性，因为它能够快速响应键值对的检索和更新需求。