java - 如何计算一组字符串的最短唯一前缀？

Question

这是命令行解析中非常常用的算法。给定一组预定义的长选项名称——计算唯一标识其中一个选项的最短前缀。例如，对于以下选项:

-help
-hostname
-portnumber
-name
-polymorphic

这将是输出:

-he
-ho
-por
-n
-pol

我正在考虑两种可能的方法——或者作为一棵树:

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

或者通过搜索子字符串:

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

所以，问题是:

1. 你会选择哪个？
2. 我是否缺少明显的第三种方式？

Answer 1

“树”解决方案是 Patricia trie 的特例(好吧，实际上它很一般) .

第一个通常查找起来更快。内存注意事项可能与您的上下文无关，因为它不会永久使用并且您只执行一次“查找”。