如何检测列表行是否被另一行前缀包含？并实现高效的行移除方案

我明白你的需求——你想要过滤掉列表里所有被其他更短的行完全匹配前缀的行，而且行内元素的顺序必须严格保持。你原来的嵌套循环写法确实会因为重复检查和低效的去重逻辑，导致运行速度变慢，尤其是当列表规模变大的时候。

问题分析 #

原代码的核心问题在于：

• 双重循环遍历所有行对，做了很多不必要的重复判断（比如x和y互相检查）；
• 使用list1[x] not in remove_lines这种列表包含判断，每次都是O(n)的时间复杂度，进一步拖慢了速度。

优化思路 #

我们可以通过排序+集合存储的方式大幅提升效率：

1. 先把所有行转换成元组（因为列表不能被哈希，无法存入集合），然后按行的长度从小到大排序。这样我们只需要用短行去检查长行的前缀，避免反向的无效判断；
2. 维护一个keep集合来存储需要保留的短行，遍历每一行时，只要检查是否存在任意一个已保留的短行是当前行的前缀——如果存在，就标记当前行为待移除；否则将当前行加入keep集合。

实现代码 #

list1 = [["0","0","0","0","0"], ["0","0","0","0","0","0"], ["0","0","0","0","0","275"], ["0","0","0","0","0","275","275"], ["0","0","0","0","275"], ["0","0","0","0","275","275"], ["0","0","0","0","275","990"], ["0","0","0","0","275","990","990"], ["0","0","0","0","275","990","2761"], ["0","0","0","0","275","990","2761","2761"], ["0","0","0","0","688"], ["0","0","0","0","688","688"], ["0","0","0","0","688","1940"], ["0","0","0","0","688","1940","1940"], ["0","0","0","0","688","1940","5041"], ["0","0","0","0","688","1940","5041","5041"], ["0","0","0","165","165","165"], ["0","0","0","165","165","165","165"]]

# 转换为元组以便哈希存储和快速比较
tuple_rows = [tuple(row) for row in list1]
# 按行长度升序排序，优先处理短行
tuple_rows.sort(key=lambda r: len(r))

keep = set()
to_remove = []

for row in tuple_rows:
    # 检查当前行是否有任何短行前缀匹配
    remove_flag = False
    for short_row in keep:
        if len(short_row) < len(row) and row[:len(short_row)] == short_row:
            remove_flag = True
            break  # 找到匹配就停止检查，提升效率
    if remove_flag:
        to_remove.append(row)
    else:
        keep.add(row)

# 输出待移除的行（转换回列表格式）
for row in to_remove:
    print(f"lines to be removed: {list(row)}")

为什么这个方案更高效？ #

• 排序优化：排序的时间复杂度是O(n log n)，之后的遍历只需要处理短行对长行的前缀检查，避免了原代码O(n²)的全量行对遍历；
• 集合存储：keep集合的添加和遍历效率更高，而且一旦找到匹配的短行就立刻停止检查，减少了不必要的比较；
• 避免重复判断：排序后短行先被加入keep，长行只需要检查已有的短行，不会出现反向的无效判断。

运行这段代码后，输出结果会和你预期的完全一致，同时处理大规模数据时的速度会有明显提升。

内容的提问来源于stack exchange，提问作者Afrim Ra