原根

题目:
给出n个只包含小写字母'a'~'z'的字符串，我们称一个字符串为原根，当且仅当给出的其他任何字符串都不是它的前缀。

案例
输入：3,["a","ab","ba"]
返回值：2
说明："a"是原根因为"a"是"ab"的前缀，所以"ab"不是原根"ba"是原根

方法一 暴力

暴力的遍历每一个字符串与其他字符串是否为该字符串的前缀即可，如果存在有一个字符串为该字符串的前缀则该字符串不是原根

class Solution {
public:
int solve(int n, vector<string>& s) {
        // write code here
        int ans = 0;
        for(int i = 0; i < s.size(); i ++){ //循环所有字符串判断第i个字符有没有前缀字符串
            int fase = 1;
            for(int j = 0; j < s.size(); j ++){ // 循环除i以外的所有字符串
                if(i != j){
                    int tt = 1;
                    for(int k = 0; k < min(s[i].size(), s[j].size()); k ++){ //判断前缀是否相同
                        if(s[j][k] != s[i][k]){
                            tt = 0; break;
                        }
                    }
                    if(tt && s[j].size() < s[i].size()){ //如果前缀相同且i的字符串大于j的字符串则j是i的前缀则该字符串不能记录答案
                        fase = 0; break;
                    }
                }
            }
            ans += fase;
        }
        return ans;
    }
};

时间复杂度: 遍历每个字符串i在对除i外的字符串进行匹配前缀
空间复杂度: 只使用若干个变量

方法二: 字典树

将所有的字符串存入字典树中,并且对于每个字符串的结束位做标记,之后在对每个字符串进行字典树遍历如果遍历过程中遍历到了有标记的位置则该字符串不是原根

class Solution {
public:
    int tree[10001][30], cnt[10000];
    int idx = 0;
    int push(string a){ //字典树的插入操作
        int p = 0;
        int fase = 1;
        for(int i = 0; i < a.size(); i ++){
            int st = a[i] - 'a';
            if(!tree[p][st]) tree[p][st] = ++ idx; //如果该位没有标记过则更新标记位
            if(cnt[p]) fase = 0; //如果前面出现过字符串则不是为原根将标记记为0
            p = tree[p][st];
        }
        if(cnt[p] > 1) fase = 0; //如果前面出现过字符串则不是为原根将标记记为0
        cnt[p] ++; //标记该位是否为字符串的结尾
        return fase;
    }
    int solve(int n, vector<string>& s) {
        // write code here
        for(int i = 0; i < n; i ++ ) push(s[i]);
        int ans = 0;
        for(int i = 0; i < s.size(); i ++) ans += push(s[i]); 
        return ans;
    }
};

时间复杂度: 字典树存储时需要遍历字符的长度并且有n个字符
空间复杂度: 字典树存储节点大小