LeetCode 2416. 字符串的前缀分数和

2416. 字符串的前缀分数和

 

 

【Trie】用字典树来存字符串，在插入的过程中把所有经过的节点的cnt + 1，然后再遍历一遍取节点的cnt即可。

class Solution {
 
    // trie
    // 2:50 13
 
    class Node {
        int cnt;
        Node[] nodes = new Node[26];
    }
 
    Node root = new Node();
 
    void insert(String word) {
        Node p = root;
        for (var i = 0; i < word.length(); i++) {
            int j = word.charAt(i) - 'a';
            if (p.nodes[j] == null) {
                Node node = new Node();
                p.nodes[j] = node;
            }
            p = p.nodes[j];
            p.cnt += 1;
        }
    }
 
    int search(String word) {
        Node p = root;
        int res = 0;
        for (var i = 0; i < word.length(); i++) {
            int j = word.charAt(i) - 'a';
            p = p.nodes[j];
            res += p.cnt;
        }
        return res;
    }
 
    public int[] sumPrefixScores(String[] words) {
        int n = words.length;
        int[] ans = new int[n];
        for (var word: words) insert(word);
        for (var i = 0; i < n; i++) {
            ans[i] = search(words[i]);
        }
        return ans;
    }
}