How to compute shortest unique prefixes of a set of strings?

Question

It's a pretty common algorithm in command line parsing. Given a set of predefined long option names -- compute the shortest prefix that uniquely identifies one of these options. So for instance, for the following options:

-help
-hostname
-portnumber
-name
-polymorphic

This would be the output:

-he
-ho
-por
-n
-pol

I'm thinking two possible ways of doing this -- either 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, question is:

1. Which would you go for?
2. Am I missing an obvious third way?

Answer 1

The "tree" solution is a special case (well, actually it's pretty general) of a Patricia trie.

The first will generally be faster to lookup. The memory considerations probably aren't relevant to your context, since it's not permanently used and you're only performing the "lookup" once.

Answer 2

I'd do the tree, looks fine.

You could build up a hash of every possible distinct substring.

Hashmap<String, String> validSubs = new Hashmap<String, String>();
HashSet<String> usedSubs = new HashSet<String>();

for (String option : options) {
  for(int i = 0; i <= option.length; i++) {
    String sub = option.substring(0, i);
    if(usedSubs.contains(sub)) {
      validSubs.remove(sub);
    } else {
      validSubs.add(sub, option);
      usedSubs.add(sub);
    }
  }
}

Answer 3

Oh, yeah, the most obvious missing answer is to use a library that already does this. http://stackoverflow.com/questions/367706/is-there-a-good-command-line-argument-parser-for-java