leetcode | 609.在系统中查找重复文件

609.在系统中查找重复文件

题目描述

给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容的文件。
输入列表中的单个目录信息字符串的格式如下：
“root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)”
这意味着有 n 个文件（f1.txt, f2.txt … fn.txt 的内容分别是 f1_content, f2_content … fn_content）在目录 root/d1/d2/…/dm 下。注意：n>=1 且 m>=0。如果 m=0，则表示该目录是根目录。
该输出是重复文件路径组的列表。对于每个组，它包含具有相同内容的文件的所有文件路径。文件路径是具有下列格式的字符串：
“directory_path/file_name.txt”

示例 1：
输入：
[“root/a 1.txt(abcd) 2.txt(efgh)”, “root/c 3.txt(abcd)”, “root/c/d 4.txt(efgh)”, “root 4.txt(efgh)”]
输出：
[[“root/a/2.txt”,”root/c/d/4.txt”,”root/4.txt”],[“root/a/1.txt”,”root/c/3.txt”]]

题目链接

思路

1.哈希表
首先我们通过字符串操作获取目录路径、文件名和文件内容。我们使用哈希映射（HashMap）来寻找重复文件，哈希映射中的键（key）是文件内容，值（value）是存储路径和文件名的列表。
我们遍历每一个文件，并把它加入哈希映射中。在这之后，我们遍历哈希映射，如果一个键对应的值列表的长度大于 1，说明我们找到了重复文件，可以把这个列表加入到答案中。

代码

class Solution(object):
    def findDuplicate(self, paths):
        """
        :type paths: List[str]
        :rtype: List[List[str]]
        """
        map = {}
        for path in paths:
            values = path.split(" ")
            for i in range(1, len(values)):
                name_cont = values[i].split('(')[-1]
                name_cont = name_cont.replace(')', '')
                value_list = map.get(name_cont, [])
                value_list.append(values[0] + '/' + values[i].split('(')[0])
                map[name_cont] = value_list
        res = []
        for key in map.keys():
            if len(map.get(key)) > 1:
                res.append(map.get(key))

        return res


if __name__ == '__main__':
    slt = Solution()
    result = slt.findDuplicate(["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"])
    print(result)