PotatoChat

498. PotatoChat重复文件检测

作者：

user

在

你说的“PotatoChat重复文件检测”通常是指那类“根据文件内容找重复文件”的题（类似 LeetCode 609）。下面给出问题描述、思路、复杂度分析以及 Python 实现（可直接用于 LeetCode 风格输入或读 stdin 的题目）。

498. PotatoChat重复文件检测

问题（常见形式）

  • 输入若干条字符串，每条表示一个目录及其下若干文件，格式如：
    "root/a 1.txt(abcd) 2.txt(efgh)"
    每条先是目录路径，然后若干个文件名和括号内的文件内容。
  • 要求把内容相同的文件分成一组，返回所有组（每组至少包含 2 个文件），每个元素为文件的完整路径 "directory/filename"。

思路

  • 遍历每一条输入字符串，解析出目录和文件项。
  • 对每个文件，提取内容作为 key，将完整路径加入 map[key] 的列表。
  • 最后把值列表长度大于 1 的加入答案。
  • 若文件内容非常大，可用内容的哈希（例如 MD5/SHA1）作为 key，但要注意哈希冲突（一般可忽略或做二次校验）。

时间和空间复杂度

  • 时间：O(N * L) —— N 为文件数，L 为平均文件描述长度（解析 + 内容长度）；若使用哈希，计算哈希也需读内容。
  • 空间：O(N * C) —— C 为保存内容/哈希所需空间（如果保留原始内容则是内容大小）。

Python 实现（函数式，LeetCode 风格）

from collections import defaultdict

def findDuplicate(paths):
    """
    paths: List[str], each like "root/a 1.txt(abcd) 2.txt(efgh)"
    return: List[List[str]]
    """
    content_map = defaultdict(list)
    for entry in paths:
        parts = entry.split()
        if not parts: 
            continue
        directory = parts[0]
        for file_descr in parts[1:]:
            # file_descr like "1.txt(abcd)"
            # find '('
            i = file_descr.find('(')
            j = file_descr.rfind(')')
            if i == -1 or j == -1 or j <= i:
                continue
            filename = file_descr[:i]
            content = file_descr[i+1:j]
            fullpath = directory + '/' + filename
            content_map[content].append(fullpath)

    # collect groups with more than one file
    res = [group for group in content_map.values() if len(group) > 1]
    return res

如果题目输入形式是先给一个整数 n，随后 n 行描述目录，你可以这样读 stdin：

import sys

lines = []
n = int(sys.stdin.readline().strip())
for _ in range(n):
    lines.append(sys.stdin.readline().rstrip('\n'))
print(findDuplicate(lines))

大文件或真实文件系统场景

  • 如果是在真实文件系统中比对实际文件（不是在单行描述里给出内容），先用文件大小筛选，再对大小相同的文件计算哈希（如 MD5），最后对哈希相同的做逐字节比较以避免哈希碰撞。

如果你有具体的输入格式或样例，贴出来我可以给出更贴合的代码或测试用例。

更多文章