力扣2416.字符串的前缀分数和
-
字典树
- add时记录分数
- 最后把一条路径上的全部分数求和加入res即可
-
class Solution {public:vector<int> sumPrefixScores(vector<string>& words) {struct Node{Node* son[26]{};int score = 0;};Node* root = new Node();for(string word:words){auto cur = root;for(char c:word){c -= 'a';if(cur->son[c] == NULL)cur->son[c] = new Node();cur = cur->son[c];cur->score ++;}}int n = words.size();vector<int> res(n);for(int i=0;i<n;i++){auto cur = root;for(char c:words[i]){cur = cur->son[c-'a'];res[i] += cur->score;}}return res;}};