如何计算最短的唯一$ P $一组字符串的pfixes？ [英] How to compute shortest unique prefixes of a set of strings?

问题描述

这是一个pretty的常见算法的命令行解析。给定一组predefined长选项的名称 - 计算最短preFIX唯一标识这些选项之一。因此，例如，下列选项：

  -help
-HostName
-portnumber
-名称
-polymorphic
 

这将输出：

  -he
浩
-POR
-n
-POL
 

我想这样做的两种可能的方式 - 无论是作为一棵树：

  *
             / | \
            / | \
           H N P
          / \ |
         Ë○○
                  / \
                 R L
 

或搜索字符串：

 的（的String：字符串）{
   的for（int i = 1; I＆LT; s.length（）; S ++）{
      如果（搜索（字符串，s.substring（0，i））的== 1）{
          result.add（s.substring（0，I）;
          打破;
      }
   }
}
 

所以，问题是：

1. 这将你去？
2. 在我缺少一个明显的第三条道路？

解决方案

树的解决方案是一个的帕特里夏·特里。

第一个一般会被更快的查找。内存方面的考虑可能是不相关的上下文，因为它不是永久使用，你只执行查找一次。

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?

解决方案

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.

这篇关于如何计算最短的唯一$ P $一组字符串的pfixes？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！