这是命令行解析中非常常见的算法.给定一组预定义的长选项名称 – 计算唯一标识其中一个选项的最短前缀.例如,对于以下选项：
-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;
}
}
}
所以,问题是：
>你会去哪个？
>我错过了明显的第三种方式吗？
解决方法
“树”解决方案是
Patricia trie的特殊情况(实际上它非常普遍).
第一个通常会更快查找.内存注意事项可能与您的上下文无关,因为它不是永久使用的,而您只执行一次“查找”.