Skip to content

609. Find Duplicate File in System 👎

  • Time: $O(n)$
  • Space: $O(n)$
 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
28
29
30
31
32
class Solution {
 public:
  vector<vector<string>> findDuplicate(vector<string>& paths) {
    vector<vector<string>> ans;
    unordered_map<string, vector<string>> contentToFilePaths;

    for (const string& path : paths) {
      istringstream iss(path);
      string rootPath;
      iss >> rootPath;  // "root/d1/d2/.../dm"

      string fileAndContent;
      while (iss >> fileAndContent) {  // "fn.txt(fn_content)"
        const int l = fileAndContent.find('(');
        const int r = fileAndContent.find(')');
        // "fn.txt"
        const string file = fileAndContent.substr(0, l);
        // "fn_content"
        const string content = fileAndContent.substr(l + 1, r - l - 1);
        // "root/d1/d2/.../dm/fn.txt"
        const string filePath = rootPath + '/' + file;
        contentToFilePaths[content].push_back(filePath);
      }
    }

    for (const auto& [_, filePaths] : contentToFilePaths)
      if (filePaths.size() > 1)
        ans.push_back(filePaths);

    return ans;
  }
};

 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
28
29
30
class Solution {
  public List<List<String>> findDuplicate(String[] paths) {
    List<List<String>> ans = new ArrayList<>();
    Map<String, List<String>> contentToFilePaths = new HashMap<>();

    for (final String path : paths) {
      final String[] words = path.split(" ");
      final String rootPath = words[0]; // "root/d1/d2/.../dm"
      for (int i = 1; i < words.length; ++i) {
        final String fileAndContent = words[i]; // "fn.txt(fn_content)"
        final int l = fileAndContent.indexOf('(');
        final int r = fileAndContent.indexOf(')');
        // "fn.txt"
        final String file = fileAndContent.substring(0, l);
        // "fn_content"
        final String content = fileAndContent.substring(l + 1, r);
        // "root/d1/d2/.../dm/fn.txt"
        final String filePath = rootPath + '/' + file;
        contentToFilePaths.putIfAbsent(content, new ArrayList<>());
        contentToFilePaths.get(content).add(filePath);
      }
    }

    for (List<String> filePaths : contentToFilePaths.values())
      if (filePaths.size() > 1)
        ans.add(filePaths);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def findDuplicate(self, paths: list[str]) -> list[list[str]]:
    contentToPathFiles = collections.defaultdict(list)

    for path in paths:
      words = path.split(' ')
      rootPath = words[0]  # "root/d1/d2/.../dm"
      for fileAndContent in words[1:]:  # "fn.txt(fn_content)"
        l = fileAndContent.find('(')
        r = fileAndContent.find(')')
        # "fn.txt"
        file = fileAndContent[:l]
        # "fn_content"
        content = fileAndContent[l + 1:r]
        # "root/d1/d2/.../dm/fn.txt"
        filePath = rootPath + '/' + file
        contentToPathFiles[content].append(filePath)

    return [filePath for filePath in contentToPathFiles.values() if len(filePath) > 1]