从列表中删除所有字符串项，它们是列表中其他字符串项的前缀

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

我不喜欢 "invent the wheel" 和实现前缀树，而是使用已经做到这一点的 python 包。

谢谢！

Answer 1

如果您的列表已经订购，则每一项都是以下各项的前缀或不是以下任何一项的前缀。

因此，你可以这样写：

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 2

我不知道有任何软件包，但应该这样做：

#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

我觉得这可以通过使用子字符串来解决，即您要查找的字符串不是任何其他字符串的子字符串。

这是 java 中的解决方案，您可以在 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]

从列表中删除所有字符串项，它们是列表中其他字符串项的前缀

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

python

algorithm

prefix-tree