LeetCode: Longest Common Prefix in Java | Param's Blog

1. Create Trie data structure
2. Initialize with the input Strings
3. Search for longest common prefix until word is completed or there is nothing left.

    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length <= 0){
            return "";
        }
        Trie trie = new Trie();
        for(int i = 0; i < strs.length; i++){
            trie.insert(strs[i]);
            if(strs[i].equals("") || strs[i].length() <= 0){
                return "";
            }
        }
        
        return trie.longestPrefix();
    }

class Trie{
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    public Trie(String s){
        root = new TrieNode();
        root.insert(s);
    }
    
    public void insert(String s){
        root.insert(s);   
    }
    
    public String longestPrefix(){
        StringBuilder prefix = new StringBuilder();
        TrieNode node = root;
        while(node != null && node.children.keySet().size() == 1 && !node.isWord){
            Set set = node.children.keySet();
            for(Iterator itr = set.iterator();itr.hasNext();){
                node = node.children.get(itr.next());
            }
            prefix.append(node.val);
        }
        return prefix.toString();
    }
}
class TrieNode{
    char val;
    boolean isWord;
    HashMap children = new HashMap();
    
    public void insert(String s){
        if(s == null || s.length() <=0){
            isWord = true;
            return;
        }
        char curr = s.charAt(0);
        TrieNode child = null;
        if(children.containsKey(curr)){
            child = children.get(curr);
            
        }else{
            child = new TrieNode();
            child.val = curr;
            children.put(curr, child);
        }
        String remainder = s.substring(1);
        child.insert(remainder);
        
    }

Also read http://fisherlei.blogspot.com/2012/12/leetcode-longest-common-prefix.html
Read full article from LeetCode: Longest Common Prefix in Java | Param's Blog