编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

 

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Tire tire=new Tire();
        int size=strs.length;
        for(String str:strs){
            tire.insert(str);
        }
        String flagStr=strs[0];
        String result="";
        String find="";
        for(int j=0;j<flagStr.length();j++){
              find+=flagStr.charAt(j);
              int pass=tire.getPreNumber(find);
           if(pass==size){
               result+=flagStr.charAt(j);
           }
        }
        return result;
        

    }

   public class TireNode{
       public int pass;
       public int end;
       public TireNode[] nexts=new TireNode[26];
   }

    public class Tire{

        private TireNode root;
        public Tire(){
            root=new TireNode();
        }

        public void insert(String word){
            if(word==null){
                return;
            }
            TireNode node=root;
            node.pass++;
            int index=0;
            char[] chs=word.toCharArray();
        
        
            for(int i=0;i<chs.length;i++){
                index=chs[i]-'a';
                if(node.nexts[index]==null){
                    node.nexts[index]=new TireNode();
                }
                node=node.nexts[index];
                node.pass++;
            }
            node.end++;

        }

        public int getPreNumber(String word){
            if(word==null){
                return 0;
            }
            char[] chs=word.toCharArray();
            int index=0;
            TireNode node=root;
            for(int i=0;i<chs.length;i++){
                index=chs[i]-'a';
                if(node.nexts[index]==null){
                    return 0;
                }
                node=node.nexts[index];
            }
            return node.pass;


        }

    }
}