My Java Solution using Trie


  • 0
    J
    public class Solution {
        class TrieNode{
            List<String> startswith;
            TrieNode [] children;
            public TrieNode(){
                children = new TrieNode[26];
                startswith = new ArrayList<>();
            }
        }
        class Trie{
            TrieNode root;
            public Trie(String [] strs){
                 root= new TrieNode();
                for(String s : strs){
                    TrieNode cur = root;
                    for(char c : s.toCharArray()){
                        int id = c -'a';
                        if(cur.children[id] ==null){
                            cur.children[id] = new TrieNode();
                        }
                        cur.children[id].startswith.add(s);
                        cur = cur.children[id];
                    }
                }
            }
            
            public int findPrefix(String prefix){
                TrieNode cur = root;
                for(char c : prefix.toCharArray()){
                    int id = c -'a';
                    if(cur.children[id]==null){
                        return 0;
                    }
                    cur = cur.children[id];
                }
                return cur.startswith.size();
            }
        }
        public String longestCommonPrefix(String[] strs) {
            if(strs==null || strs.length ==0){
                return "";
            }
            Arrays.sort(strs,new Comparator<String>(){
               @Override
               public int compare(String a, String b){
                   return -Integer.compare(a.length(),b.length());
               }
            });
            int max = 0;
            Trie trie = new Trie(strs);
            for(int i=0;i<strs[0].length();i++){
                int len = trie.findPrefix(strs[0].substring(0,strs[0].length() - i));
                if(len == strs.length){
                    max = Math.max(max,strs[0].length() - i);
                }
            }
            return strs[0].substring(0,max);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.