Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths.
A group of duplicate files consists of at least two files that have exactly 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 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 group 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: ["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"]]
Note:
Algorithm
For the brute force solution, firstly we obtain the directory paths, the filenames and file contents separately by appropriately splitting the elements of the list. While doing so, we keep on creating a which contains the full path of every file along with the contents of the file. The contains data in the form .
Once this is done, we iterate over this . For every element chosen from the list, we iterate over the whole to find another element whose file contents are the same as the element. For every such element found, we put the element's file path in a temporary list and we also mark the element as visited so that this element isn't considered again in the future. Thus, when we reach the end of the array for every element, we obtain a list of file paths in , which have the same contents as the file corresponding to the element. If this list isn't empty, it indicates that there exists content duplicate to the element. Thus, we also need to put the element's file path in the .
At the end of each iteration, we put this list obtained in the resultant list and reset the list for finding the duplicates of the next element.
Complexity Analysis
Time complexity : . Creation of will take , where n is the number of directories and x is the average string length. Every file is compared with every other file. Let files are there with average size of , then files comparision will take , equals can take . Here, Worst case will be when all files are unique.
Space complexity : . Size of lists and can grow upto .
In this approach, firstly we obtain the directory paths, the file names and their contents separately by appropriately splitting each string in the given list. In order to find the files with duplicate contents, we make use of a HashMap , which stores the data in the form . Thus, for every file's contents, we check if the same content already exist in the hashmap. If so, we add the current file's path to the list of files corresponding to the current contents. Otherwise, we create a new entry in the , with the current contents as the key and the value being a list with only one entry(the current file's path).
At the end, we find out the contents corresponding to which atleast two file paths exist. We obtain the resultant list , which is a list of lists containing these file paths corresponding to the same contents.
The following animation illustrates the process for a clearer understanding.
!?!../Documents/609_Find_Duplicate.json:1000,563!?!
Complexity Analysis
Time complexity : . strings of average length is parsed.
Space complexity : . and size grows upto .
Analysis written by: @vinod23