Remove all string items from a list, that are prefix of other string items in the list

Question

I've got a list fo paths, and I'd like to keep only the items that are not prefix of any other item.

For example, In the following list:

private
private/etc
private/etc/pam.d
usr
usr/local
usr/local/lib
usr/local/lib/security

I want to keep only:

private/etc/pam.d
usr/local/lib/security

I prefer not to "invent the wheel" and implement prefix tree, but using a python package that already do this.

thanks!

Answer 1

If your list is already ordered, each item is a prefix of the following OR is not a prefix of any of the following.

Therefore, you can write:

ls.sort()
[ls[i] for i in range(len(ls))[:-1] if ls[i] != ls[i+1][:len(ls[i])]] + [ls[-1]]

Another implementation, using zip:

[x for x, y in zip(ls[:-1], ls[1:]) if x != y[:len(x)]] + [ls[-1]]

Answer 2

I don't know of any packages, but this should do it:

#a is the list of items
for i in range(len(a)):
    for j in range(i, len(a)):
        if (a[i] in a[j]) and len(a[i]) < len(a[j]):
            a[i] = 'delete'

a = [i for i in a if i!= 'delete'] #new list without prefixed elements

Answer 3

I feel this can be solved by using sub-string, i.e. you are looking for a string which is not a sub-string of any other string.

Here is a solution in java, you can use same logic in python.

public static void findFullyQualifiedPaths() {

    List<String> paths = new ArrayList<>();
    paths.add("private");
    paths.add("private/etc");
    paths.add("private/etc/pam.d");
    paths.add("usr");
    paths.add("usr/local");
    paths.add("usr/local/lib");
    paths.add("usr/local/lib/security");

    System.out.println("Input Paths");
    System.out.println(paths);

    List<String> filteredPaths = new ArrayList<String>(paths);

    filteredPaths.removeIf(currentPath -> {
        for (String path : paths) {
            if ((!path.equals(currentPath)) && path.contains(currentPath)) {
                return true;
            }
        }
        return false;
    });
    System.out.println("Paths after removing the substrings");
    System.out.println(filteredPaths);
}

Output:

Input Paths
[private, private/etc, private/etc/pam.d, usr, usr/local, usr/local/lib, usr/local/lib/security]
Paths after removing the substrings
[private/etc/pam.d, usr/local/lib/security]