题意

一个大小为$nn$n的字符串数组，默认所有贡献为1，如果一个字符串$s_{i}s\_i$si​是$s_{j}s\_j$sj​的前缀，那么$s_{j}s\_j$sj​贡献为0

求所有字符串的贡献和

范围: $n\le 10^{5}n\backslash leq\; 10^5$n≤105 字符串所有字符总数$\le 10^6\backslash leq\; 10^6$≤106

解法

暴力模拟

我们把题意翻译成代码，两两做对比，并用一个数组记录是不是有其它字符串时自己的前缀。最后把这个记录数组统计一下

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @param s string字符串一维数组 
# @return int整型
#
class Solution:
    def solve(self , n , s ):
        root = [1 for i in range(n)]
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if s[i].startswith(s[j]):
                    root[i] = 0
        return sum(root)

复杂度分析

时间复杂度: 我们遍历了每一对，即使比较前缀是常数代价，也达到了$O\left(n^2\right)O(n^2)$O(n2)，而startswith还与字符串长度有关，在最坏情况每个字符都参与了比较，一个字符最多比较$n-1n-1$n−1次，所以复杂度为$O(n\cdot \sum s_i)O(n\; \backslash cdot\; \backslash sum\; \{s\_i\})$O(n⋅∑si​)，虽然通过了测试点，但如果数据更大就会超时，应该是数据比较弱

空间复杂度: 我们记录了贡献数组,其它都是常数个临时变量，$O\left(n\right)O(n)$O(n)

桶排序

代码

回想桶排序，比如拿到一组数，我们以十进制作为桶的划分

123461 123 124444 123500

我们 首先比较他们的最高位, 按照最高位分桶, 这里我们关心第6位

这样完成了按照第6位分桶

然后我们看第digit=1的桶里的，再按第5位分桶

恰好第5位都是2，全部在一起

然后我们看第digit=2的桶里的，再按第4位分桶

这时两个是3，一个是4，又分开了它们，再按第3位

然后我们看第digit=2的桶里的，再按第4位分桶

至此我们对所有数完成了分割。

上面的操作说明了，每次分割桶的时候，就是数字开始不同的时候。

回到题目，虽然这里是'a'-'z'的字符串，但逻辑是类似的，同时字符串相对于高位补零来说，有自己特殊的“字符串结束”的信息

以 样例为例 "a","ab","ba"

1. "a","ab"在桶"a"里,"ba" 在桶"b"里
2. 对第二层，"a" 分到了 字符结束桶 里，而"ab"分到了"b"桶里

这里注意到的是，字符串长度可能短于分割时的，不像数字可以高位认为是零。而正是这特殊情况的分割，分割到字符结束桶里的，表明一个字符串是另一个字符串的前缀。

在上面样例中是"a"在第二个字符分割时被分到了 字符结束桶里

所以注意对字符串的长度判断和处理：多个相同的字符串之间互为前缀，所以这种情况下，它们以及它们本来开始分割的桶就都不会是原根

以上就完成了题目

class Solution {
public:
    // 统计不是root的个数
    long long f(int chidx,vector<string *>& sref){
        // 27个桶，前面分别对应字符，最后一个对应**字符结束桶**
        vector<vector<string *> > alphabet(27,vector<string *>());
        for(auto sitr:sref){
            if(sitr->size() == chidx){
                alphabet[26].push_back(sitr); // **字符结束桶**
            }else{
                alphabet[(*sitr)[chidx]-'a'].push_back(sitr); // 'a' - 'z' 桶
            }
        }
        // 存在一个字符结束
        if(alphabet[26].size() > 1)return sref.size(); // **字符结束桶** 里的是其它剩余的前缀，且 // **字符结束桶** 里有多余一个，所以内部互为前缀
        if(alphabet[26].size() == 1)return sref.size() - 1; // **字符结束桶** 里的是其它剩余的前缀
        long long result = 0;
        for(int ch=0;ch<26;ch++){ // 每个桶内 再下一层分桶
            if(alphabet[ch].size() < 2)continue; // 空桶和只有一个元素的桶 不需要再分割
            result += f(chidx+1,alphabet[ch]);
        }
        return result;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串vector 
     * @return int长整型
     */
    int solve(int n, vector<string>& s) {
        vector<string *> sref = {};
        for(int i =0;i<n;i++){
            sref.push_back(&s[i]);
        }
        return n - f(0,sref); // 所有减去不是 原根 的
    }
};

复杂度分析

时间复杂度: 初始化会建立字符串指针数组。我们在函数的第$ii$i层，对当前桶内的每一个字符串的第$ii$i位进行分割到桶，桶的个数是$26+1=2726+1=27$26+1=27个,常数个，也就是我们总的遍历的是所有字符串的每一位至多1次,所以复杂度是$O(n+\sum S_i)O(n+\backslash sum\; S\_i)$O(n+∑Si​)

空间复杂度: 顶层建立了n个桶，每一次函数调用有初始化的27个桶，因为每多一个长度会多一次调用，同一位上字符不同会多一次调用，所有层被调用的次数不大于所有字符串字符数，每一次判断第$ii$i个字符串的第$jj$j个字符就会发生一次分桶，也就是把指针放进桶里的操作，所以总次数也是所有字符串的字符数量和。所以总空间复杂度$O(n+\sum S_i)O(n+\backslash sum\; S\_i)$O(n+∑Si​)