Hard

题目描述

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

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

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

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 是 "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。

解题思路

思路分析：

暴力解法是对每一对 (i,j) 都检查 words[i] 是否是 words[j] 的前缀和后缀，时间复杂度为 O(n²·m)，会超时。

优化思路 - 字典树（Trie）：

关键观察：如果一个字符串 s1 同时是另一个字符串 s2 的前缀和后缀，那么对于 s1 的每个位置 k，都有 s1[k] == s2[k] 且 s1[k] == s2[s2.length - s1.length + k]。

我们可以构建一个特殊的字典树，其中每个节点存储一个字符对 (prefix_char, suffix_char)：

  1. 对于字符串 s，在位置 i 处，我们存储字符对 (s[i], s[s.length - 1 - i])
  2. 这样，如果 s1 是 s2 的前缀和后缀，那么 s1 对应的字符对序列一定是 s2 对应序列的前缀

算法流程：

  1. 从左到右处理每个字符串
  2. 对于当前字符串，先在字典树中查询，统计有多少个之前的字符串是当前字符串的前缀和后缀
  3. 然后将当前字符串插入字典树

每个字典树节点维护一个计数器，表示以该节点结尾的字符串数量。在插入过程中，累加路径上遇到的所有计数器值。

推荐解法： 字典树解法，时间复杂度 O(总字符数)，空间复杂度 O(总字符数)。

代码实现

class Solution {
public:
    long long countPrefixSuffixPairs(vector<string>& words) {
        struct TrieNode {
            map<pair<char, char>, TrieNode*> children;
            int count = 0;
        };
        
        TrieNode* root = new TrieNode();
        long long result = 0;
        
        for (const string& word : words) {
            int n = word.length();
            TrieNode* curr = root;
            
            // 查询阶段：统计有多少个之前的字符串是当前字符串的前缀和后缀
            for (int i = 0; i < n; i++) {
                pair<char, char> p = {word[i], word[n - 1 - i]};
                if (curr->children.find(p) == curr->children.end()) {
                    break;
                }
                curr = curr->children[p];
                result += curr->count;
            }
            
            // 插入阶段：将当前字符串插入字典树
            curr = root;
            for (int i = 0; i < n; i++) {
                pair<char, char> p = {word[i], word[n - 1 - i]};
                if (curr->children.find(p) == curr->children.end()) {
                    curr->children[p] = new TrieNode();
                }
                curr = curr->children[p];
            }
            curr->count++;
        }
        
        return result;
    }
};

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.count = 0
        
        root = TrieNode()
        result = 0
        
        for word in words:
            n = len(word)
            curr = root
            
            # 查询阶段：统计有多少个之前的字符串是当前字符串的前缀和后缀
            for i in range(n):
                p = (word[i], word[n - 1 - i])
                if p not in curr.children:
                    break
                curr = curr.children[p]
                result += curr.count
            
            # 插入阶段：将当前字符串插入字典树
            curr = root
            for i in range(n):
                p = (word[i], word[n - 1 - i])
                if p not in curr.children:
                    curr.children[p] = TrieNode()
                curr = curr.children[p]
            curr.count += 1
        
        return result

public class Solution {
    public long CountPrefixSuffixPairs(string[] words) {
        var root = new TrieNode();
        long result = 0;
        
        foreach (string word in words) {
            int n = word.Length;
            var curr = root;
            
            // 查询阶段：统计有多少个之前的字符串是当前字符串的前缀和后缀
            for (int i = 0; i < n; i++) {
                var p = new KeyValuePair<char, char>(word[i], word[n - 1 - i]);
                if (!curr.children.ContainsKey(p)) {
                    break;
                }
                curr = curr.children[p];
                result += curr.count;
            }
            
            // 插入阶段：将当前字符串插入字典树
            curr = root;
            for (int i = 0; i < n; i++) {
                var p = new KeyValuePair<char, char>(word[i], word[n - 1 - i]);
                if (!curr.children.ContainsKey(p)) {
                    curr.children[p] = new TrieNode();
                }
                curr = curr.children[p];
            }
            curr.count++;
        }
        
        return result;
    }
    
    public class TrieNode {
        public Dictionary<KeyValuePair<char, char>, TrieNode> children = new Dictionary<KeyValuePair<char, char>, TrieNode>();
        public int count = 0;
    }
}

var countPrefixSuffixPairs = function(words) {
    class TrieNode {
        constructor() {
            this.children = new Map();
            this.count = 0;
        }
    }
    
    const root = new TrieNode();
    let result = 0;
    
    for (const word of words) {
        const n = word.length;
        let curr = root;
        
        // 查询阶段：统计有多少个之前的字符串是当前字符串的前缀和后缀
        for (let i = 0; i < n; i++) {
            const p = word[i] + '|' + word[n - 1 - i];
            if (!curr.children.has(p)) {
                break;
            }
            curr = curr.children.get(p);
            result += curr.count;
        }
        
        // 插入阶段：将当前字符串插入字典树
        curr = root;
        for (let i = 0; i < n; i++) {
            const p = word[i] + '|' + word[n - 1 - i];
            if (!curr.children.has(p)) {
                curr.children.set(p, new TrieNode());
            }
            curr = curr.children.get(p);
        }
        curr.count++;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(∑len(words[i]))需要遍历所有字符串的所有字符，每个字符的插入和查询操作都是O(1)
空间复杂度O(∑len(words[i]) × 字符集大小²)字典树存储字符对，最坏情况下每个字符对都不同

相关题目