题解 | #原根#

思路：

题目的主要信息：

• n个字符串，只有小写字母a-z
• 如果对于一个字符串，其他n-1个字符串都不是它的前缀，则它是原根
• 求这n个字符串中原根的数量

方法一：暴力法
具体做法：
我们可以暴力遍历每一个字符串，然后再分别与其他n-1个字符串进行比较，检查是否是它的前缀。检查前缀的时候，我们可以也是暴力比较前面每一个字符串是否相同。

class Solution {
public:
    bool judge(string& s1, string& s2){ //判断s1是不是s2的前缀
        if(s1.length() > s2.length()) //s1较长直接返回
            return false;
        int i;
        for(i = 0; i < s1.length(); i++){
            if(s1[i] != s2[i])
                break;
        }
        if(i == s1.length())  //前缀
            return true;
        else
            return false;
    }
    int solve(int n, vector<string>& s) {
        int res = 0;
        for(int i = 0; i < n; i++){ //遍历所有字符串
            bool flag = true;
            for(int j = 0; j < n; j++){ //与其他所有字符串比较
                if(i == j)  //不与自己比较
                    continue;
                if(judge(s[j], s[i])){ //是前缀
                    flag = false;
                    break;
                }
            }
            if(flag)
                res++;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，两层循环为，其中次判断相当于遍历所有字符串的所有字符
• 空间复杂度：，无额外空间使用

方法二：字典树
具体做法：
我们可以参考相似和 的解法，同样是字符串重复地进行两两比较，可以采用字典树。
首先我们对所有字符串按照长度排序（等长则按照字典序，使相同的串务必相邻），这样每次遍历到一个字符串的时候，它前面的才有可能成为它的前缀，而后面的都不可能成为它的前缀，当然我们要排除掉串相同的情况。于是，我们每遍历到一个字符串时只需要每次判断字典树中的是否有自己的前缀，然后再将自己加入字典树中。
我们以两个字母的示例为图：

struct Tree{
        Tree* letter[26]; //26个小写字母
        bool isend;  //是否末尾
        Tree(){    //初始化函数
            for(int i = 0; i < 26; i++)
                letter[i] = NULL;
            isend = false;
        }
};
class Solution {
public:
    static bool comp(string& s1, string& s2){ //重载比较，按长度排序，长度相同则字典序
        return s1.length() == s2.length() ? s1 < s2 : s1.length() < s2.length();
    }
    void add(Tree* root, string s){ //字符串s加入字典树
        for(int i = 0; i < s.length(); i++){
            if(root->letter[s[i] - 'a'])
                root = root->letter[s[i] - 'a'];//字母已经存在
            else{ //字母不存在，要开辟空间
                for(; i < s.length(); i++){
                    Tree* p = new Tree();
                    root->letter[s[i] - 'a'] = p;
                    root = root->letter[s[i] - 'a'];
                }
                root->isend = true; //字符串结尾
                break;
            }
        }
    }
    bool find(Tree* root, string s){ //现有字典树查找是否有s的前缀
        for(int i = 0; i < s.length(); i++){ 
            if(root->letter[s[i] - 'a']){ //存在这个节点
                if(root->letter[s[i] - 'a']->isend) //结尾
                    return true;
                root = root->letter[s[i] - 'a']; //继续往下
            }
            else  //不存在这个节点，不是前缀
                return false;
        }
        return false;
    }
    int solve(int n, vector<string>& s) {
        Tree* root = new Tree();
        int res = 0;
        sort(s.begin(), s.end(), comp); //按长度排序
        for(int i = 0; i < n; i++){ //遍历每一个字符串
            bool flag = false;
            while(i + 1 < n && s[i].length() == s[i + 1].length() && s[i] == s[i + 1]){ //排除后面有与它相同字符春的情况
                i++;
                flag = true;
            }
            if(!flag) //当没有和自己重复的字符串才进行查找
                if(!find(root, s[i])) //查找是否有前缀
                    res++; 
            add(root, s[i]); //将这个字符串加入字典树
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，相当于遍历所有的字符串，加上sort函数的排序
• 空间复杂度：，树空间最深处为最长字符串的长度