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

发布时间：2020-12-15 00:46:08 所属栏目：Java 来源：网络整理

导读：这是命令行解析中非常常见的算法.给定一组预定义的长选项名称 – 计算唯一标识其中一个选项的最短前缀.例如,对于以下选项： -help-hostname-portnumber-name-polymorphic 这将是输出： -he-ho-por-n-pol 我正在考虑两种可能的方法 – 作为一棵树： * / | /

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

-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的特殊情况(实际上它非常普遍).

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!