题目分析

本题是第311场周赛的第四题，难度不大，考察的是字符串的前缀问题，看到字符串的前缀小伙伴们想到了什么算法？

前缀树(Trie)

本题不是简单的Trie，增加了一点点的难度，要统计树中以某个前缀为根的子树数量。如果有不明白的小伙伴可以先去学习Trie。

因此在插入的时候就可以统计出每个节点的子树数量，只要插入的时候让每个节点对应数量+1即可。在查找以某个字符串作为前缀时，直接找到该节点取出数量即可。

因为本题是找列表中以某个字符串的所有前缀为前缀的数量。因此对于字符串”abc”来说，要找以”a”、”ab”、”abc”为前缀的数量。因此就是从trie树种递归查找节点对应的子树数量。

算法的**时间复杂度为O(n^2)，空间复杂度为O(n^2)**。

class Trie {
    private Trie[] children;
    private int childNum;

    public Trie() {
        children = new Trie[26];
        childNum = 0;
    }

    public void insert(String word) {
        Trie node = this;
        node.childNum++;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
            node.childNum++;
        }
    }

    public int search(String word) {
        Trie node = this;
        int cnt = 0;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return cnt;
            }
            node = node.children[index];
            cnt += node.childNum;
        }
        return cnt;
    }
}

class Solution {
    public int[] sumPrefixScores(String[] words) {
        int n = words.length;
        Trie trie = new Trie();
        for (String s : words) {
            trie.insert(s);

        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            String s = words[i];
            res[i] = trie.search(s);
        }
        return res;
    }
}

刷题总结

小伙伴们遇到字符串的前缀问题，一定要想到使用Trie树。