Medium

题目描述

给定一个目录信息列表，包括目录路径和该目录中所有文件的内容，返回文件系统中所有重复文件的路径。你可以按任意顺序返回答案。

一组重复文件至少包含两个内容相同的文件。

输入列表中的单个目录信息字符串具有以下格式：

"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

这意味着在目录 “root/d1/d2/…/dm” 中有 n 个文件（f1.txt, f2.txt … fn.txt），分别具有内容（f1_content, f2_content … fn_content）。注意 n >= 1 且 m >= 0。如果 m = 0，则意味着该目录就是根目录。

输出是重复文件路径的分组列表。对于每组，它包含具有相同内容的所有文件的路径。文件路径是具有以下格式的字符串：

"directory_path/file_name.txt"

示例 1：

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

示例 2：

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

约束：

  • 1 <= paths.length <= 2 * 10^4
  • 1 <= paths[i].length <= 3000
  • 1 <= sum(paths[i].length) <= 5 * 10^5
  • paths[i] 由英文字母、数字、’/’、’.’、’(’、’)’ 和 ’ ’ 组成
  • 可以假设同一目录中没有文件或目录共享相同的名称
  • 可以假设每个给定的目录信息代表一个唯一的目录。单个空格分隔目录路径和文件信息

解题思路

这道题的核心思路是使用哈希表来分组相同内容的文件。

解题步骤：

  1. 解析路径字符串：对于每个目录信息字符串，需要提取目录路径和其中的文件信息。字符串格式为 “目录路径 文件1(内容1) 文件2(内容2) …”

  2. 提取文件信息：对于每个文件信息部分，需要解析出文件名和文件内容。文件信息格式为 “filename.txt(content)”

  3. 使用哈希表分组：以文件内容作为键，将具有相同内容的文件路径存储在同一个列表中

  4. 筛选结果：只返回包含至少两个文件路径的组

实现细节：

  • 使用空格分割目录路径和文件信息
  • 使用括号定位文件内容的开始和结束位置
  • 构建完整的文件路径：目录路径 + “/” + 文件名

这种方法的时间复杂度主要取决于字符串解析的过程，空间复杂度取决于存储的文件路径数量。

代码实现

class Solution {
public:
    vector<vector<string>> findDuplicate(vector<string>& paths) {
        unordered_map<string, vector<string>> contentToFiles;
        
        for (const string& path : paths) {
            int spacePos = path.find(' ');
            string directory = path.substr(0, spacePos);
            string fileInfo = path.substr(spacePos + 1);
            
            stringstream ss(fileInfo);
            string file;
            while (ss >> file) {
                int openParen = file.find('(');
                int closeParen = file.find(')');
                
                string fileName = file.substr(0, openParen);
                string content = file.substr(openParen + 1, closeParen - openParen - 1);
                string fullPath = directory + "/" + fileName;
                
                contentToFiles[content].push_back(fullPath);
            }
        }
        
        vector<vector<string>> result;
        for (const auto& pair : contentToFiles) {
            if (pair.second.size() > 1) {
                result.push_back(pair.second);
            }
        }
        
        return result;
    }
};

class Solution:
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        content_to_files = {}
        
        for path in paths:
            parts = path.split(' ')
            directory = parts[0]
            
            for i in range(1, len(parts)):
                file_info = parts[i]
                open_paren = file_info.find('(')
                close_paren = file_info.find(')')
                
                file_name = file_info[:open_paren]
                content = file_info[open_paren + 1:close_paren]
                full_path = directory + "/" + file_name
                
                if content not in content_to_files:
                    content_to_files[content] = []
                content_to_files[content].append(full_path)
        
        result = []
        for content, files in content_to_files.items():
            if len(files) > 1:
                result.append(files)
        
        return result

public class Solution {
    public IList<IList<string>> FindDuplicate(string[] paths) {
        Dictionary<string, List<string>> contentToFiles = new Dictionary<string, List<string>>();
        
        foreach (string path in paths) {
            string[] parts = path.Split(' ');
            string directory = parts[0];
            
            for (int i = 1; i < parts.Length; i++) {
                string fileInfo = parts[i];
                int openParen = fileInfo.IndexOf('(');
                int closeParen = fileInfo.IndexOf(')');
                
                string fileName = fileInfo.Substring(0, openParen);
                string content = fileInfo.Substring(openParen + 1, closeParen - openParen - 1);
                string fullPath = directory + "/" + fileName;
                
                if (!contentToFiles.ContainsKey(content)) {
                    contentToFiles[content] = new List<string>();
                }
                contentToFiles[content].Add(fullPath);
            }
        }
        
        IList<IList<string>> result = new List<IList<string>>();
        foreach (var kvp in contentToFiles) {
            if (kvp.Value.Count > 1) {
                result.Add(kvp.Value);
            }
        }
        
        return result;
    }
}

var findDuplicate = function(paths) {
    const contentToFiles = new Map();
    
    for (const path of paths) {
        const parts = path.split(' ');
        const directory = parts[0];
        
        for (let i = 1; i < parts.length; i++) {
            const fileInfo = parts[i];
            const openParen = fileInfo.indexOf('(');
            const closeParen = fileInfo.indexOf(')');
            
            const fileName = fileInfo.substring(0, openParen);
            const content = fileInfo.substring(openParen + 1, closeParen);
            const fullPath = directory + "/" + fileName;
            
            if (!contentToFiles.has(content)) {
                contentToFiles.set(content, []);
            }
            contentToFiles.get(content).push(fullPath);
        }
    }
    
    const result = [];
    for (const [content, files] of contentToFiles) {
        if (files.length > 1) {
            result.push(files);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N × M)N 为路径总数，M 为平均每个路径中的字符数
空间复杂度O(N × M)存储所有文件路径和内容的哈希表空间

相关题目