Find Duplicate File in System

Problem Statement

In this task, you are provided with a list known as paths. Each item in the list consists of directory information which includes both the directory path and details about the files contained within it, specifically their names and contents. The goal is to identify sets of files across potentially multiple directories that have exactly the same content, and return these sets grouped by their paths.

Each directory entry in the list is structured to show multiple files belonging to it. Here's how the format is laid out:

• The string begins with the full path to the directory, followed by a listing of files. Each file is represented by its name, immediately followed by its content in parentheses.

For instance, in a string format such as "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)", the path root/d1/d2/.../dm indicates where the files are stored, and each fn.txt(fn_content) describes a file fn.txt with the content fn_content.

The result should be a collection of groups. Each group will contain the complete paths for files that share the same content, thus indicating these files as duplicates.

Examples

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"]]

Example 2

Input:

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

Output:

[["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Constraints

• 1 <= paths.length <= 2 * 104
• 1 <= paths[i].length <= 3000
• 1 <= sum(paths[i].length) <= 5 * 105
• paths[i] consist of English letters, digits, '/', '.', '(', ')', and ' '.
• You may assume no files or directories share the same name in the same directory.
• You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info.

Approach and Intuition

Given the nature of the problem, our main goal is to efficiently map file content to their respective paths and then identify which contents are associated with multiple paths. Here’s the approach in a step-by-step manner:

1. Initialize a Dictionary: Create a dictionary to store file content as keys and a list of paths (that end in the filename) as values. This dictionary acts as a way to quickly map and reference file content to where it exists in the file system.

2. Parse Input: Iterate through each directory info string in the paths list. For each string:

   • Split the string by spaces initially to separate the directory path from the file descriptors.
   • For each file descriptor, separate the filename from its content, and construct the full path for each file.
   • Populate the dictionary with the file content as the key and append the constructed path to the respective list.

3. Identify Duplicates: After constructing the dictionary, we then filter out entries where the list of paths is greater than one. These are our duplicates because more than one path means the same file content was found in different places.

4. Output Format: Format the final output as required; a list of lists, where each sub-list contains file paths that share the same content.

By approaching the solution in this manner, we are leveraging the dictionary for both quick lookups and straightforward grouping of similar content, thus handling potentially large datasets in an efficient manner. This method ensures that all parts of the input are processed only once in a sequential manner, promoting efficiency regarding time complexity.

Solutions

public class Solution {
    public List<List<String>> findDuplicates(String[] filePaths) {
        HashMap<String, List<String>> contentMap = new HashMap<>();
        for (String filePath: filePaths) {
            String[] segments = filePath.split(" ");
            for (int i = 1; i < segments.length; i++) {
                String[] fileData = segments[i].split("\\(");
                fileData[1] = fileData[1].replace(")", "");
                List<String> paths = contentMap.getOrDefault(fileData[1], new ArrayList<String>());
                paths.add(segments[0] + "/" + fileData[0]);
                contentMap.put(fileData[1], paths);
            }
        }
        List<List<String>> duplicates = new ArrayList<>();
        for (List<String> values: contentMap.values()) {
            if (values.size() > 1)
                duplicates.add(values);
        }
        return duplicates;
    }
}