当前位置：首页 > article >正文

LeetCode3045.统计前后缀下标对II

article 2025/1/4 16:47:17

统计字符串数组中的前缀-后缀对 —— 利用字符串哈希优化

在处理字符串相关的问题时，哈希技术常常能够提供高效的解决方案。本文将介绍一个具体的应用场景：给定一个字符串数组，统计满足特定前缀和后缀条件的字符串对的数量。我们将深入解析这个问题，并通过代码示例展示如何利用字符串哈希技术实现高效的解决方案。

问题描述

给定一个下标从 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 <= 10^5
1 <= words[i].length <= 10^5
words[i] 仅由小写英文字母组成。
所有 words[i] 的长度之和不超过 5 * 10^5。

解决思路

这道题目考察了字符串哈希的应用，特别是如何高效地统计满足前缀和后缀条件的字符串对。我们可以通过以下步骤来解决：

字符串哈希基础: 将每个字符串视为一个基于某个素数（如 P = 131）的多项式表达式，并对其进行模运算（如 MOD = 10^9 + 7）以计算哈希值。这样可以将字符串转换为一个唯一的数值表示，便于快速比较。
前缀和后缀哈希: 对于每个字符串，我们需要分别计算其所有可能的前缀和后缀的哈希值。前缀哈希可以通过从左到右累积计算，而后缀哈希则需要从右到左累积计算。
哈希值存储与计数: 使用一个哈希表（如 unordered_map）来存储已经计算过的前缀哈希值及其出现次数。当遍历到新的字符串时，检查其每一个前缀哈希值是否在哈希表中出现过，从而统计满足条件的字符串对。

关键代码解析

以下是实现上述思路的关键代码片段，特别是 left 和 right 哈希值的计算：

typedef long long LL;
class Solution {
public:

    long long h[100010];
    long long countPrefixSuffixPairs(vector<string>& words) {
        unordered_map<LL,LL> mp;
        int n = words.size(), P = 131, MOD = 1e9 + 7;
        h[0] = 1;
        long long res = 0;
        for(int i = 1; i <= 100000;i ++)h[i] = (h[i-1] * P) %MOD;
        for(int i = 0; i < n; i ++)
        {
            
            string s1 = words[i];
            int len = s1.size();
            LL left = 0, right = 0;
            for(int j = 0, k = len - 1;j < len; j ++ , k --)
            {
                left = ( (left * P) % MOD + s1[j] ) % MOD;
                right = ((s1[k] * h[j]) %MOD + right) % MOD;
                if(left == right && mp[left])
                {
                    res += mp[left];
                }
            }
            mp[left] = mp[left] + 1;

        }
        return res;
    }
};

`left` 的计算

left = ( (left * P) % MOD + s1[j] ) % MOD;

目的: 计算当前字符串 s1 的前缀哈希值。
过程:
1. 初始化 left = 0。
2. 对于字符串中的每一个字符 s1[j]，将当前的 left 乘以基数 P，然后加上当前字符的 ASCII 值。
3. 对结果进行模运算，确保哈希值不会过大。

示例:
对于字符串 "abc"：

j=0: left = ('a')
j=1: left = ('a' * 131 + 'b')
j=2: left = (('a' * 131 + 'b') * 131 + 'c')

`right` 的计算

right = ((s1[k] * h[j]) % MOD + right) % MOD;

目的: 计算当前字符串 s1 的后缀哈希值。
过程:
1. 初始化 right = 0。
2. 从字符串的末尾开始，逐个字符向前遍历（k = len - 1 到 0）。
3. 对于每一个字符 s1[k]，将其乘以预计算的 h[j]（即 P^j % MOD，其中 j 是当前字符在后缀中的位置），然后加上之前的 right。
4. 对结果进行模运算，确保哈希值不会过大。