2416. 字符串的前缀分数之和

Hard

题目描述

给你一个由 n 个非空字符串组成的数组 words。

定义字符串 term 的分数等于以 term 作为前缀的 words[i] 的数目。

例如，如果 words = ["a", "ab", "abc", "cab"]，那么 "ab" 的分数是 2，因为 "ab" 是 "ab" 和 "abc" 的一个前缀。

返回一个长度为 n 的数组 answer，其中 answer[i] 是 words[i] 的每个非空前缀的分数之和。

**注意：**字符串视作它自身的一个前缀。

示例 1：

输入：words = ["abc","ab","bc","b"]
输出：[5,4,3,2]
解释：每个字符串的答案如下：
- "abc" 有 3 个前缀："a"、"ab" 和 "abc"。
- 2 个字符串的前缀为 "a"，2 个字符串的前缀为 "ab"，1 个字符串的前缀为 "abc"。
总和为 answer[0] = 2 + 2 + 1 = 5。
- "ab" 有 2 个前缀："a" 和 "ab"。
- 2 个字符串的前缀为 "a"，2 个字符串的前缀为 "ab"。
总和为 answer[1] = 2 + 2 = 4。
- "bc" 有 2 个前缀："b" 和 "bc"。
- 2 个字符串的前缀为 "b"，1 个字符串的前缀为 "bc"。
总和为 answer[2] = 2 + 1 = 3。
- "b" 有 1 个前缀："b"。
- 2 个字符串的前缀为 "b"。
总和为 answer[3] = 2。

示例 2：

输入：words = ["abcd"]
输出：[4]
解释：
"abcd" 有 4 个前缀 "a"、"ab"、"abc" 和 "abcd"。
每个前缀的分数都是 1，所以总和为 answer[0] = 1 + 1 + 1 + 1 = 4。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 由小写英文字母组成。

解题思路

这是一道典型的前缀树（Trie）应用题。我们需要统计每个前缀在所有字符串中出现的次数。

思路分析

暴力解法：对于每个字符串的每个前缀，遍历所有字符串统计该前缀的出现次数。时间复杂度为 O(n²m²)，其中 n 是字符串个数，m 是平均字符串长度。
前缀树优化：使用 Trie 数据结构可以高效地处理前缀问题：
- 构建 Trie 时，在每个节点记录通过该节点的字符串数量
- 对于每个字符串的每个前缀，可以直接从 Trie 中查询该前缀的出现次数

算法步骤

构建前缀树：将所有字符串插入 Trie，每个节点维护一个计数器记录经过该节点的字符串数量
查询前缀分数：对于每个字符串，遍历其所有前缀，在 Trie 中查询每个前缀的计数，累加得到该字符串的总分数

这种方法的关键在于 Trie 节点的计数器，它记录了有多少个字符串的前缀经过了该节点，这样我们就能在 O(m) 时间内查询任意前缀的出现次数。

推荐解法：前缀树解法，时间复杂度 O(nm)，空间复杂度 O(nm)，是最优解。

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[26] = {};
        int count = 0;
    };
    
    vector<int> sumPrefixScores(vector<string>& words) {
        TrieNode* root = new TrieNode();
        
        // 构建前缀树
        for (const string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                int idx = c - 'a';
                if (!node->children[idx]) {
                    node->children[idx] = new TrieNode();
                }
                node = node->children[idx];
                node->count++;
            }
        }
        
        // 计算每个字符串的前缀分数之和
        vector<int> result;
        for (const string& word : words) {
            TrieNode* node = root;
            int sum = 0;
            for (char c : word) {
                int idx = c - 'a';
                node = node->children[idx];
                sum += node->count;
            }
            result.push_back(sum);
        }
        
        return result;
    }
};

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.count = 0
        
        root = TrieNode()
        
        # 构建前缀树
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                node.count += 1
        
        # 计算每个字符串的前缀分数之和
        result = []
        for word in words:
            node = root
            total = 0
            for char in word:
                node = node.children[char]
                total += node.count
            result.append(total)
        
        return result

public class Solution {
    public class TrieNode {
        public TrieNode[] Children = new TrieNode[26];
        public int Count = 0;
    }
    
    public int[] SumPrefixScores(string[] words) {
        TrieNode root = new TrieNode();
        
        // 构建前缀树
        foreach (string word in words) {
            TrieNode node = root;
            foreach (char c in word) {
                int idx = c - 'a';
                if (node.Children[idx] == null) {
                    node.Children[idx] = new TrieNode();
                }
                node = node.Children[idx];
                node.Count++;
            }
        }
        
        // 计算每个字符串的前缀分数之和
        int[] result = new int[words.Length];
        for (int i = 0; i < words.Length; i++) {
            TrieNode node = root;
            int sum = 0;
            foreach (char c in words[i]) {
                int idx = c - 'a';
                node = node.Children[idx];
                sum += node.Count;
            }
            result[i] = sum;
        }
        
        return result;
    }
}

var sumPrefixScores = function(words) {
    class TrieNode {
        constructor() {
            this.children = {};
            this.count = 0;
        }
    }
    
    const root = new TrieNode();
    
    // 构建前缀树
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
            node.count++;
        }
    }
    
    // 计算每个字符串的前缀分数之和
    const result = [];
    for (const word of words) {
        let node = root;
        let sum = 0;
        for (const char of word) {
            node = node.children[char];
            sum += node.count;
        }
        result.push(sum);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(nm)	n 为字符串个数，m 为所有字符串长度之和。构建 Trie 和查询都需要遍历所有字符
空间复杂度	O(nm)	Trie 树的节点数最多为所有字符串的字符总数

题目描述#

解题思路#

思路分析#

算法步骤#

代码实现#

复杂度分析#

相关题目#