Elegant Solution Use a Trie


  • 2
    K
    public class Solution {
        
        public class TrieNode{
            private final HashMap<Character,TrieNode> next= new HashMap<Character,TrieNode>();
            int count= 0;
        }
        
        private TrieNode root = new TrieNode();
        
        public void buildTrie(String... words){
            TrieNode node;
            for(String word: words){
                node= root;
                node.count++;
                for(char c: word.toCharArray()){
                    if(!node.next.containsKey(c))
                        node.next.put(c, new TrieNode());
                    node= node.next.get(c);
                    node.count++;
                }
            }
        }
        
        public String getLongestPrefix(int wordsDictSize){
            StringBuilder sn= new StringBuilder();
            TrieNode node= root;
            Character c;
            while(node.next.size() == 1){
                c= node.next.keySet().iterator().next();//toArray(new Character[0])[0];
                if( node.next.get(c).count != wordsDictSize )
                    break;
                sn.append(c);
                node= node.next.get(c);
            }
            return sn.toString();
        }
        
        public String longestCommonPrefix(String[] strs) {
            if(strs == null)
                return null;
            buildTrie(strs);
            return getLongestPrefix(strs.length);
        }
    }

Log in to reply
 

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