# 609. Find Duplicate File in System

• Time: $O(|\texttt{paths}|)$
• Space: $O(|\texttt{paths}|)$
  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> findDuplicate(vector& paths) { vector> ans; unordered_map> 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> findDuplicate(String[] paths) { List> ans = new ArrayList<>(); Map> 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 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]