import java.util.ArrayList;
import java.util.List;

/**
 * Created by silence on 10/21/17.
 */
class TrieNode {
    int freq;
    TrieNode[] children = new TrieNode[26];

    TrieNode() {
        freq = 0;
        for (TrieNode t : children) {
            t = null;
        }
    }

}

public class AllCommonPrefixs {


    static TrieNode buildTrie(String[] dict) {
        TrieNode root = new TrieNode();
        TrieNode cur;
        for (String s : dict) {
            cur = root;
            for (char c : s.toCharArray()) {
                if (cur.children[c - 'a'] == null) {
                    cur.children[c - 'a'] = new TrieNode();
                }
                cur.children[c - 'a'].freq++;
                cur = cur.children[c - 'a'];
            }
        }

        return root;
    }

    static List<String> findAllCommonPrefixs(String[] dict) {
        List<String> ret = new ArrayList<>();
        TrieNode root = buildTrie(dict);
        dfs(root, new StringBuilder(), ret);
        return ret;
    }

    static void dfs(TrieNode root, StringBuilder sb, List<String> ret) {

        if (root.freq == 1) {
            ret.add(sb.toString());
            return;
        }
        for (int i = 0; i < root.children.length; ++i) {
            if (root.children[i] == null) continue;
            char tem = (char) (i + 'a');
            //  System.out.print(tem);
            sb.append(tem);
            dfs(root.children[i], sb, ret);
            sb.deleteCharAt(sb.length() - 1);
        }

    }

    public static void main(String[] args) {
        String[] testcase = {"apple", "pinetree", "pie", "pineapple", "dog", "god", "dizz"};
        List<String> res = findAllCommonPrefixs(testcase);
        for (String s : res) {
            System.out.print(s + ", ");
        }
        System.out.println();


    }
}

• http://www.geeksforgeeks.org/find-all-shortest-unique-prefixes-to-represent-each-word-in-a-given-list/