元宝 LeetCode 2416.字符串的前缀分数和 C++实现

下面给你LeetCode 2416《字符串的前缀分数和》的C 标准实现思路仍然是Trie 前缀计数时间复杂度最优 ✅✅ C 实现推荐写法#include bits/stdc.h using namespace std; class Solution { private: struct TrieNode { int cnt 0; TrieNode* children[26] {nullptr}; }; TrieNode* root new TrieNode(); // 插入单词到 Trie void insert(const string word) { 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-cnt; // 经过该前缀的单词数 1 } } // 计算单个单词的前缀分数 int query(const string word) { TrieNode* node root; int score 0; for (char c : word) { node node-children[c - a]; score node-cnt; } return score; } public: vectorint sumPrefixScores(vectorstring words) { // 建 Trie for (const string w : words) { insert(w); } // 计算结果 vectorint ans(words.size()); for (int i 0; i words.size(); i) { ans[i] query(words[i]); } return ans; } }; 复杂度分析项目复杂度构建 TrieO(总字符数)查询O(总字符数)空间O(总字符数)✅适用于最大数据规模10⁵ 字符串 示例words {abc,ab,bc,b} 输出 {5, 4, 3, 2} 为什么 C 写法高效使用数组指针TrieNode* children[26]无unordered_map开销内存连续缓存友好完全符合 LeetCode 判题性能要求✅ 可选优化进阶使用静态数组 索引池避免new更快使用vectorint代替指针竞赛常用如果你需要✅静态数组版最快✅内存释放版✅Python / Java 对照版✅一步步手动画 Trie可以直接告诉我