题解 | #原根#

题意整理

• 给定一个大小为n的字符串数组。
• 找出字符串数组中原根的个数。
• 给定一个字符串，其他任何字符串都不是它的前缀，则称为原根。

方法一（暴力法）

1.解题思路

直接遍历整个字符串数组，然后将当前字符串，与所有其他字符串进行比较，只要其他字符串中有一个是它的前缀，就不是原根，原根标记置为false。每次都判断原根标记是否为true，如果为true，则计数加一。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串一维数组 
     * @return int整型
     */
    public int solve (int n, String[] s) {
        //初始化计数变量
        int cnt=0;
        for(int i=0;i<n;i++){
            //判断是否是原根
            boolean originRoot=true;
            for(int j=0;j!=i&&j<n;j++){
                //如果某个字符串能在s[i]第一个位置找到，说明是s[i]的前缀
                if(s[i].indexOf(s[j])==0){
                    originRoot=false;
                }
            }
            //如果所有其他字符串都是s[i]的前缀，则s[i]是原根
            if(originRoot){
                cnt++;
            }
        }
        return cnt;
    }
}

3.复杂度分析

• 时间复杂度：假设每个字符串的长度是m，indexOf()的时间复杂度是，总共需要判断次，所以最终的时间复杂度是 ，其中 是所有字符串的长度之和。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度是。

方法二（字典树）

1.解题思路

首先将所有字符串插入字典树，通过字典树存储每个节点访问次数。然后检查每个字符串，如果字符串对应路径上所有节点访问次数等于1，或者字符串对应路径上所有节点访问次数大于1，则这个字符串是原根。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param s string字符串一维数组 
     * @return int整型
     */
    public int solve (int n, String[] s) {
        //初始化字典树
        Trie trie=new Trie();
        for(int i=0;i<n;i++){
            //往字典树中插入字符串
            trie.insert(s[i]);
        }

        int res=0;
        for(int i=0;i<n;i++){
            //判断某个字符串是否是原根
            if(trie.originRoot1(s[i])||trie.originRoot2(s[i])){
                res++;
            }
        }
        return res;        
    }
}

class Trie{
    //子节点数组
    Trie[] child;
    //子节点访问次数
    int cnt;

    Trie(){
        this.child=new Trie[26];
        this.cnt=0;
    }

    public void insert(String s){
        //从根节点开始遍历
        Trie node=this;
        for(char c:s.toCharArray()){
            //如果为空，就新建节点
            if(node.child[c-'a']==null){
                node.child[c-'a']=new Trie();
            }
            //往子节点方向遍历
            node=node.child[c-'a'];
            //访问次数加一
            node.cnt++;
        }
    }

    //字符串所有节点访问次数大于1(比如["a","ab","ba"]中的"a")
    public boolean originRoot1(String s){
        Trie node=this;
        for(char c:s.toCharArray()){
            node=node.child[c-'a'];
            if(node.cnt!=1){
                return false;
            }
        }
        return true;
    }

    //字符串所有节点访问次数等于1(比如["a","ab","ba"]中的"ba")
    public boolean originRoot2(String s){
        Trie node=this;
        for(char c:s.toCharArray()){
            node=node.child[c-'a'];
            if(node.cnt==1){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

• 时间复杂度：假设 是所有字符串的长度之和，字典树中插入的节点个数最多为，每次插入和检查的时间复杂度都是对应字符串的长度，所以时间复杂度是 。
• 空间复杂度：需要额外大小为的空间存储节点，而每个节点还自带一个child数组(数组大小为26)，所以空间复杂度是 。