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

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的一个特例(嗯,实际上它非常普遍).

第一个通常会更快查找.内存考虑可能与您的上下文无关,因为它不是永久使用的,而您只执行一次"查找".