在系统中查找重复文件

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

一、题目描述

给你一个目录信息列表 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;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。