CODEWITHSUNDEEP
javaalgorithmstring
Asgeir S. Nilsen
Asgeir S. Nilsen

Reputation: 1137

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

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?

Upvotes: 7

Views: 4178

Answers (3)

ykaganovich
ykaganovich

Reputation: 14964

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);
    }
  }
}

Upvotes: 0

Mark Peters
Mark Peters

Reputation: 81074

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.

Upvotes: 5

ykaganovich
ykaganovich

Reputation: 14964

Oh, yeah, the most obvious missing answer is to use a library that already does this. How to parse command line arguments in Java?

Upvotes: 0

Related Questions