|
5 | 5 | import java.util.List; |
6 | 6 | import java.util.Map; |
7 | 7 |
|
8 | | -/** |
9 | | - * 609. Find Duplicate File in System |
10 | | - * |
11 | | - * Given a list of directory info including directory path, and all the files with contents in this directory, |
12 | | - * you need to find out all the groups of duplicate files in the file system in terms of their paths. |
13 | | - * A group of duplicate files consists of at least two files that have exactly the same content. |
14 | | -
|
15 | | - A single directory info string in the input list has the following format: |
16 | | -
|
17 | | - "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" |
18 | | -
|
19 | | - It means there are n files (f1.txt, f2.txt ... fn.txt with content f1_content, f2_content ... fn_content, respectively) |
20 | | - in directory root/d1/d2/.../dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory. |
21 | | -
|
22 | | - The output is a list of group of duplicate file paths. |
23 | | - For each group, it contains all the file paths of the files that have the same content. |
24 | | - A file path is a string that has the following format: |
25 | | -
|
26 | | - "directory_path/file_name.txt" |
27 | | -
|
28 | | - Example 1: |
29 | | -
|
30 | | - Input: |
31 | | - ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"] |
32 | | -
|
33 | | - Output: |
34 | | - [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]] |
35 | | -
|
36 | | - Note: |
37 | | - No order is required for the final output. |
38 | | - You may assume the directory name, |
39 | | - file name and file content only has letters and digits, and the length of file content is in the range of [1,50]. |
40 | | -
|
41 | | - The number of files given is in the range of [1,20000]. |
42 | | - You may assume no files or directories share the same name in a same directory. |
43 | | -
|
44 | | - You may assume each given directory info represents a unique directory. Directory path and file infos are separated by a single blank space. |
45 | | -
|
46 | | - Follow up beyond contest: |
47 | | - Imagine you are given a real file system, how will you search files? DFS or BFS ? |
48 | | - If the file content is very large (GB level), how will you modify your solution? |
49 | | - If you can only read the file by 1kb each time, how will you modify your solution? |
50 | | - What is the time complexity of your modified solution? What is the most time consuming part and memory consuming part of it? How to optimize? |
51 | | - How to make sure the duplicated files you find are not false positive? |
52 | | - */ |
53 | 8 | public class _609 { |
54 | 9 |
|
55 | 10 | public static class Solution1 { |
|
0 commit comments