检查列表中的元素是否是java中其他元素的前缀

Question

我想实现一个字符串列表,然后检查列表中的所有元素是否有任何元素是列表中其他元素的前缀.例如

[abc, cde, efg, cdetgh]

在上面的列表中,"cde"(一个元素)是其他元素的前缀"cdetgh".如果可能的话,我不想迭代整个列表.

Answer 1

您确实必须迭代整个列表。天真的方法将迫使您为列表中的每个元素迭代整个列表。这是一个 O(N^2) 算法。

根据列表的大小和执行此操作所需的频率，这可能是可以接受的。您可以进行权衡，以牺牲空间为代价来节省时间。遍历每个元素，并为每个元素创建每个前缀的哈希集，然后查看检查前缀中的元素。

final Map<String, List<String>> prefixes = new HashMap<>();
for (final String element : list) {
   // Go through every prefix that is at least 1 in length, 
   // but shorter than the current element).
   for (int len = 1; len < element.length() - 1; ++len) {
      final String prefix = element.substring(0, len);
      List<String> hasPrefix = prefixes.get(prefix);
      if (hasPrefix == null) {
          hasPrefix = new ArrayList<>();
          prefixes.put(prefix, hasPrefix);
      }
      hasPrefix.add(element);
   }
}

for (final String element : list) {
   if (prefixes.containsKey(element)) {
      System.out.printf("The element \"%s\" is a prefix of the following elements:\n%s", element, prefixes.get(element).toString());
   }
}

该算法的时间复杂度为 O(N*M)，其中 N 是列表大小，M 是平均元素长度。但占用的空间稍大一些。对此有更有效的解决方案，但它们变得越来越复杂，并且涉及有限状态机构造或前缀树。