在系统中查找重复文件

一、题目描述

给你一个目录信息列表 paths ，包括目录路径，以及该目录中的所有文件及其内容，请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。

一组重复的文件至少包括 两个 具有完全相同内容的文件。

输入 列表中的单个目录信息字符串的格式如下：

"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" 这意味着，在目录 root/d1/d2/.../dm 下，有 n 个文件 ( f1.txt, f2.txt ... fn.txt ) 的内容分别是 ( f1_content, f2_content ... fn_content ) 。注意：n >= 1 且 m >= 0 。如果 m = 0 ，则表示该目录是根目录。

输出 是由 重复文件路径组 构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串：

"directory_path/file_name.txt" 示例1

输入：paths = ["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"]]

示例2

输入：paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
输出：[["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]

二、思路分析

本题的输入格式为一个paths数组，数组每一项的内容为目录根路径以及该目录下的所有文件列表和文件内容信息，如:["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目录下有两个文件，分别是1.txt和2.txt，1.txt的文件内容为'abcd'，2.txt的文件内容为'efgh';
• root/c/d目录下有一个文件4.txt，内容为'efgh'；
• root目录下有一个文件4.txt，内容为'efgh'。 题目需要我们找出的是文件内容相同的文件列表，即我们需要找到文件内容相同的不同文件，并将其完整路径放入一个列表中。 看到这里，我们不难发现可以使用map哈希表来解决这道题目。
• 1、定义一个哈希表contentMap用来存放文件列表，key为文件内容，value为文件路径列表；

let contentMap = {};

• 2、遍历输入参数paths，读取每一个目录下的文件；

for(let i = 0; i < paths.length; i++){
    let path = paths[i].split(' ');
    for(let j = 1; j < path.length; j++){
        let file = path[j].split(/\(|\)/g);
        const arr = contentMap[file[1]] || [];
        arr.push(path[0] + '/' + file[0]);
        contentMap[file[1]] = arr;
    }
}

• 3、通过文件内容把每一个目录下的文件放进contentMap哈希表中去； let file = path[j].split(/\(|\)/g);通过 /(|)/ 可以分隔出文件路径和文件内容。

let path = paths[i].split(' ');
for(let j = 1; j < path.length; j++){
    let file = path[j].split(/\(|\)/g);
    const arr = contentMap[file[1]] || [];
    arr.push(path[0] + '/' + file[0]);
    contentMap[file[1]] = arr;
}

• 4、遍历哈希表contentMap，将文件路径列表大于2个的存放到返回结果中。

let res = [];
for(let k in contentMap){
    if(contentMap[k].length > 1){
        res.push(contentMap[k]);
    }
}

三、AC代码

/**
 * @param {string[]} paths
 * @return {string[][]}
 */
var findDuplicate = function(paths) {
    let contentMap = {};
    for(let i = 0; i < paths.length; i++){
        let path = paths[i].split(' ');
        for(let j = 1; j < path.length; j++){
            let file = path[j].split(/\(|\)/g);
            const arr = contentMap[file[1]] || [];
            arr.push(path[0] + '/' + file[0]);
            contentMap[file[1]] = arr;
        }
    }
    let res = [];
    for(let k in contentMap){
        if(contentMap[k].length > 1){
            res.push(contentMap[k]);
        }
    }
    return res;
};