Java – how to calculate the shortest unique prefix for a set of strings?

This is a very common algorithm in command - line parsing Given a predefined set of long option names – calculates the shortest prefix that uniquely identifies one of the options For example, for the following options:

-help
-hostname
-portnumber
-name
-polymorphic

This will be the output:

-he
-ho
-por
-n
-pol

I am considering two possible approaches – as a tree:

*
             / | \
            /  |  \
           H   N   P
          / \      |
         E   O     O
                  / \
                 R   L

Or by searching for substrings:

for (String s : strings) {
   for (int i = 1; i < s.length(); s++) {
      if (search(strings,s.substring(0,i)) == 1) {
          result.add(s.substring(0,i);
          break;
      }
   }
}

So the question is:

>Where will you go? > Did I miss the obvious third way?

Solution

The "tree" solution is a special case of Patricia trie (in fact, it is very common)

The first one is usually faster to find Memory considerations may be irrelevant to your context because it is not used permanently, and you only perform a "find" once