元宝 LeetCode 2416.字符串的前缀分数和 public int[] sumPrefixScores(String[] words)

这是LeetCode 2416Sum of Prefix Scores of Strings的经典解法说明。题意简述给你一个字符串数组words对每个单词words[i]计算所有单词中以该单词任意前缀开头的单词个数之和。返回int[]其中第i个结果对应words[i]。核心思路Trie前缀树关键观察如果一个单词A是另一个单词B的前缀那么B会贡献到A的分数中所有前缀的贡献都可以用Trie 计数解决做法一最常用 ✅Trie 记录经过次数Trie 节点设计class TrieNode { TrieNode[] children new TrieNode[26]; int count; // 有多少个单词经过这个节点 }构建 Trie对每一个word从根节点开始逐字符插入每经过一个节点count 这样每个节点的count就表示有多少个单词包含当前前缀查询结果对每个word沿着 Trie 走累加路径上所有节点的countJava 完整代码 ✅public int[] sumPrefixScores(String[] words) { TrieNode root new TrieNode(); // Build Trie for (String w : words) { TrieNode node root; for (char c : w.toCharArray()) { int idx c - a; if (node.children[idx] null) { node.children[idx] new TrieNode(); } node node.children[idx]; node.count; } } int n words.length; int[] res new int[n]; // Query for (int i 0; i n; i) { TrieNode node root; int sum 0; for (char c : words[i].toCharArray()) { node node.children[c - a]; sum node.count; } res[i] sum; } return res; } class TrieNode { TrieNode[] children new TrieNode[26]; int count; }复杂度分析项目复杂度建 TrieO(总字符数)查询O(总字符数)空间O(总字符数)✅时间 空间O(N · L)N 为单词数L 为平均长度示例words [abc,ab,bc,b] 输出[5,4,3,2]解释abc前缀a,ab,abc分别被 2、2、1 个单词共享 → 5常见优化 / 变体用数组代替 HashMap本题字符集固定a~z若内存敏感可使用压缩 Trie本题不需要如果你愿意我可以✅ 画Trie 结构示意图✅ 改写成Python / C✅ 讲解为什么不能用纯哈希直接解随时告诉我