Check if item in list is prefix of another in java

Question

I want to implement a list of strings, and then check for all elements in the list that if there is any element that is a prefix of another element in the list or not. for instance

[abc, cde, efg, cdetgh] 

in the above list, "cde" (one element) is the prefix of the other "cdetgh" element. I do not want to iterate over the entire list, if possible.

Answer 1

You need to iterate over the whole list. A naive approach will make you iterate over the entire list for each item in the list. This is O (N ^ 2) algorithm.

Depending on the size of the list and the frequency required to complete this operation, this may be acceptable. You can compromise to save time at the expense of space. Go through each element and create a hash set of each prefix for each element, and then look at the elements that are in the 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 size of the list and M is the average length of the element. But it takes a little more space. There are even more effective solutions for this, but they are becoming more complex and are associated with the construction of finite state machines or the prefix tree.