Удалить все строковые элементы из списка, которые являются префиксом других строковых элементов в списке

Question

У меня есть список путей, и я хотел бы сохранить только те элементы, которые не являются префиксами любого другого элемента.

Например, в следующем списке:

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

Я хочу сохранить только:

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

Я предпочитаю не «изобретать колесо» и использовать префикс дерево, но с использованием пакета python, который уже делает это.

спасибо!

Answer 1

Я не знаю ни одного пакета, но это должно сделать это:

#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 2

Если ваш список уже упорядочен, каждый элемент является префиксом следующего ИЛИ не является префиксом любого из следующих.

Следовательно, вы можете написать:

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

Другая реализация, использующая zip:

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

Answer 3

Я чувствую, что это можно решить с помощью подстроки, т.е. вы ищете строку, которая не является подстрокой какой-либо другой строки.

Вот решение в java, вы можно использовать те же логи c в 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);
}

Вывод:

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]