从Leetcode 每日一题练习继续讨论：
2416. 字符串的前缀分数和
2416. Sum of Prefix Scores of Strings
题解
本题是一道难题，但像这种要多次计算字符串前缀的问题我们已经熟悉了，为了避免重复遍历字符串可以使用字典树trie。在这个问题上思考一下为什么用字典树更好，如果我们用map将某个前缀作为key，其出现的次数作为value。这样对于有包含关系的前缀就会产生大量重复，同时没能充分利用前缀自身自带的字符的先后关系（字符串ab，a是在b前面且与b紧密相邻的，用字典树则将ab相邻和a在b前面这两种字符关系都表示了出来）。
熟悉字典树后，本题只需对每个字符串构建字典树，对字典树的节点做一些修改，节点中加入表示被访问到次数的count变量，无需记录节点是否为单词的结尾。构建好后对每个字符串，访问字典树，并将路径上所有节点的count相加即得最终的sum。
代码
const int ALPHABET_SIZE = 26;
struct TrieNode {
TrieNode* children[ALPHABET_SIZE];
int count;
TrieNode() : count(0) {
for(int i = 0; i < ALPHABET_SIZE; ++i){
children[i] = nullptr;
}
}
};
class Trie {
public:
TrieNode* root;
Trie() { root = new TrieNode(); }
void insert(const string &word) {
TrieNode* node = root;
for(char c : word){
int index = c - 'a';
if(index < 0 || index >= ALPHABET_SIZE){
continue;
}
if(node->children[index] == nullptr){
node->children[index] = new TrieNode();
}
node = node->children[index];
node->count++;
}
}
int count(const string &word){
int ret = 0;
TrieNode* node = root;
for(char c : word){
int index = c - 'a';
node = node->children[index];
ret += node->count;
}
return ret;
}
~Trie() {
function<void(TrieNode*)> deleteTrie = [&](TrieNode* node) {
if(node == nullptr) return;
for(int i = 0; i < ALPHABET_SIZE; ++i){
if(node->children[i] != nullptr){
deleteTrie(node->children[i]);
}
}
delete node;
};
deleteTrie(root);
}
};
class Solution {
public:
vector<int> sumPrefixScores(vector<string>& words) {
Trie *trie = new Trie();
for (string word : words){
trie->insert(word);
}
vector<int> result;
for (string word : words){
result.push_back(trie->count(word));
}
return result;
}
};