# 2416. Sum of Prefix Scores of Strings
###### tags: `Leetcode` `Hard` `Trie`
Link: https://leetcode.com/problems/sum-of-prefix-scores-of-strings/description/
## 思路
trie
每个node先记录有多少个word拥有当下这个prefix
再用trie遍历每个word都路上遇到的所有wordCount加在一起即可
## Code

class Solution {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        int wordCount = 0;
    }
    TrieNode root;
    public int[] sumPrefixScores(String[] words) {
        int n = words.length;
        root = new TrieNode();
        for(String word:words) add(word);
        int[] ans = new int[n];

        for(int i=0; i<n; i++){
            String word = words[i];
            int sum = count(word);
            ans[i] = sum;
        }
        return ans;
    }
    private void add(String s){
        TrieNode curr = root;
        for(int i=0; i<s.length(); i++){
            if(curr.children[s.charAt(i)-'a']==null) curr.children[s.charAt(i)-'a'] = new TrieNode();
            curr = curr.children[s.charAt(i)-'a'];
            curr.wordCount++;
        }
    }
    private int count(String s){
        TrieNode curr = root;
        int sum = 0;
        for(int i=0; i<s.length(); i++){
            curr = curr.children[s.charAt(i)-'a'];
            sum += curr.wordCount;
        }
        return sum;
    }
}