NC559 题解 | #原根#

题意分析

• 给我们n个字符串，对于某一个字符串，如果除了这个字符串本身之外的字符串都不是它的前缀，那么我们就称这个字符串为原根。问这n个字符串里面有多少个原根。

思路分析

解法一 暴力求解

• 首先，我们来进行暴力求解。我们先枚举每个需要进行判断的字符串a，然后枚举这个字符串之外的其他字符串b，对于两个字符串相比较，我们需要判断b是否为a字符串的前缀。直接循环遍历比较即可。

• 代码如下

  • 最外层需要枚举每个字符串，执行n次操作，需要遍历所有的字符串的所有的字符，次数为。对于里面，需要进行两两判断，循环遍历的次数就是，所以总的时间复杂度为
  • 过程中只用了少数几个变量存储，空间复杂度为$O(1)O(1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串vector 
     * @return int整型
     */
    int solve(int n, vector<string>& s) {
        // write code here
        int ans=0;
        // 判断字符串s[i]是否为原根
        for(int i=0;i<n;i++){
            bool flag=true;
            // 逐个比较不是s[i]的字符串
            for(int j=0;j<n;j++){
                if(i==j) continue;
                int len1=s[i].size();
                int len2=s[j].size();
                // 判断字符串s[j]是否为s[i]的前缀
                if(len1<len2) continue;
                int k=0;
                for(k=0;k<len2;k++){
                    if(s[i][k]!=s[j][k]){
                        break;
                    }
                }
                // 如果k可以到达len2，说明字符串s[j]是s[i]的前缀，s[i]就一定不是原根
                if(k==len2){
                    flag=false;
                    break;
                }
            }
            if(flag) ans++;
        }
        
        return ans;
    }
};

解法二 字典树

• 我们发现，上面的一种解法的时间复杂度确实很高，所以我们需要寻找更加优秀的算法解决这个问题。由于给出的字符一定是小写字母。所以我们可以对每个字符串构建一个字典树。将每个字符串放到字典树里面。然后，我们标记每个字符串的结尾的那个字符指向的指针，我们称之为终结指针。将所有的字符串都放到字典树里面之后。我们在执行一次构建字典树的过程。只是我们不去像之前那样减字典树，我们只是走一遍这个过程，然后记录这个过程中遍历得到的终结指针的个数。如果得到的个数超过了1，那么说明这个字符串存在一个字符串是它的前缀，那么它就不是原根。

• 结合下图进行理解

• 代码如下
  • 每个字符串在字典树上面的遍历的次数是字符串的长度。所以总的时间复杂度为所有的字符串的长度的和。即时间复杂度为
  • 过程中，我们开了数组来构建字符树，同时标记了终结指针，字典树的最深的深度为最长的字符串的长度。所以我们总的空间复杂度为$O(26\ast maxLen(S_i))O(26*maxLen(S\_i))$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串vector 
     * @return int整型
     */
    int tree[1000010][30];
    int ed[1000010*30]; // 表示这个指针是多少个字符串的最后的字符的指针
    int cnt=0;
    // 构建字典树
    void insert(string s){
        int p=0;
        for(auto x:s){
            if(tree[p][x-'a']==-1){
                tree[p][x-'a']=++cnt;
            }
            p=tree[p][x-'a'];
        }
        
        // 这个指向最后的指针累加1
        ed[p]++;
    }
    // 重新走一遍每个字符串构建字典树的过程，寻找路径上出现的终结结点的个数
    bool query(string s){
        int p=0;
        int sum=0; // 记录过程中遇到多少个指向最后的指针
        for(auto x:s){
            if(ed[p]){
                sum++;
            }
            p=tree[p][x-'a'];
        }
        if(ed[p]) sum++;
        // 如果遍历过的终结指针少于1个，那么说明没有任何其他字符串是它的前缀
        return sum<=1;
    }
    int solve(int n, vector<string>& s) {
        // write code here
        memset(tree,-1,sizeof(tree));
        memset(ed,0,sizeof(ed));
        
        for(auto x:s){
            insert(x);
        }
        
        int ans=0;
        for(auto x:s){
            if(query(x)) ans++;
        }
        
        return ans;
    }
};