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

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

-help -hostname -portnumber -name -polymorphic 

这将是输出：

 -he -ho -por -n -pol 

我正在考虑两种可能的方法 – 作为一棵树：

  * / | \ / | \ HNP / \ | EOO / \ RL 

或者通过搜索子串：

 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的一个特例（嗯，实际上它非常普遍）。

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

Answer 2

哦，是的，最明显的缺失答案是使用已经完成此操作的库。 如何在Java中解析命令行参数？

Answer 3

我做树，看起来很好。

您可以构建每个可能的不同子字符串的哈希值。

 Hashmap validSubs = new Hashmap(); HashSet usedSubs = new HashSet(); 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); } } }