leetcode 609. Find Duplicate File in System（找到相同的文件）

Given a list paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order.

A group of duplicate files consists of at least two files that have the same content.

A single directory info string in the input list has the following format:

“root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)”
It means there are n files (f1.txt, f2.txt … fn.txt) with content (f1_content, f2_content … fn_content) respectively in the directory “root/d1/d2/…/dm”. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

“directory_path/file_name.txt”

Example 1:

Input: paths = [“root/a 1.txt(abcd) 2.txt(efgh)”,“root/c 3.txt(abcd)”,“root/c/d 4.txt(efgh)”,“root 4.txt(efgh)”]
Output: [[“root/a/2.txt”,“root/c/d/4.txt”,“root/4.txt”],[“root/a/1.txt”,“root/c/3.txt”]]

什么叫做相同的文件？内容相同的就算相同的文件，内容就是括号里面的部分，如(f1_content)
要把相同的文件找出来（带路径），放在list里返回。

思路：

就是String的一系列操作和HashMap.

String操作体现在：
split，indexOf，substring操作
split(" “)把不同的文件名割出来，如f1.txt, f2.txt
indexOf(”(")和substring把内容割出来

HashMap操作体现在：
把内容当作key, 不同的文件名组成list当作value,

key对应的llist的size > 1时说明有相同的文件，加入结果即可。

public List<List<String>> findDuplicate(String[] paths) {
    List<List<String>> res = new ArrayList<>();
    
    HashMap<String, List<String>> map = new HashMap<>();
    
    for(String path : paths) {
        String[] subPaths = path.split(" ");
        
        String dire = subPaths[0];
        
        for(int i = 1; i < subPaths.length; i++) {
            String subPath = subPaths[i];
            
            int index = subPath.indexOf("(");
            String content = subPath.substring(index);  //包含括号，懒得再去substring(index+1, subPath.length)
            List<String> tmp = map.getOrDefault(content, new ArrayList<String>());
            tmp.add(dire + "/" + subPath.substring(0,index));
            map.put(content, tmp);
        }
    }
    
    for(List<String> files : map.values()) {
        if(files.size() > 1) res.add(files);
    }
    
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27