Check if an element in list is prefix of other in java

Question

I want to implement a list of strings and then check for all element in the list that if there is any element which is the prefix of other element in the list or not. For example

[abc, cde, efg, cdetgh]

in above list, "cde" (one element) is prefix of other element "cdetgh". I don't want to iterate whole list, if possible.

Answer 1

You do have to iterate the whole list. The naive approach will force you to iterate the whole list for every element in the list. This is an O(N^2) algorithm.

Depending on the size of the list and the frequency you need to perform this operation, that may be acceptable. You can do a trade-off to save time at the expense of space. Go through every element, and create a hashset of every prefix for every element, and then see check for elements that are in prefixes.

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());
   }
}

This algorithm is O(N*M) in time, where N is the list size, and M is the average element length. But takes up a bit more space. There are even more efficient solutions to this, but they become increasingly complex, and involve finite state machine construction, or a prefix tree.