Hard

题目描述

由于一个错误，文件系统中存在许多重复的文件夹。给你一个二维数组 paths，其中 paths[i] 是一个数组，表示文件系统中第 i 个文件夹的绝对路径。

例如，["one", "two", "three"] 表示路径 "/one/two/three"。

如果两个文件夹（不一定在同一层级）包含相同的非空相同子文件夹集合和底层子文件夹结构，则它们是相同的。文件夹不需要在根级别才能相同。如果两个或多个文件夹相同，则标记这些文件夹以及它们的所有子文件夹。

例如，下面文件结构中的文件夹 "/a" 和 "/b" 是相同的。它们（以及它们的子文件夹）都应该被标记：

/a
/a/x
/a/x/y
/a/z
/b
/b/x
/b/x/y
/b/z

但是，如果文件结构还包括路径 "/b/w"，则文件夹 "/a" 和 "/b" 就不相同了。注意 "/a/x" 和 "/b/x" 即使添加了文件夹也仍然被认为是相同的。

一旦所有相同的文件夹及其子文件夹都被标记，文件系统将删除它们所有。文件系统只运行一次删除，因此初始删除后变得相同的任何文件夹都不会被删除。

返回删除所有标记文件夹后剩余文件夹的路径的二维数组 ans。路径可以按任何顺序返回。

示例 1：

输入：paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
输出：[["d"],["d","a"]]
解释：文件结构如图所示。
文件夹 "/a" 和 "/c"（以及它们的子文件夹）被标记为删除，因为它们都包含一个名为 "b" 的空文件夹。

示例 2：

输入：paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]
输出：[["c"],["c","b"],["a"],["a","b"]]
解释：文件结构如图所示。
文件夹 "/a/b/x" 和 "/w"（以及它们的子文件夹）被标记为删除，因为它们都包含一个名为 "y" 的空文件夹。
注意文件夹 "/a" 和 "/c" 在删除后是相同的，但它们不会被删除，因为它们之前没有被标记。

提示：

  • 1 <= paths.length <= 2 * 10^4
  • 1 <= paths[i].length <= 500
  • 1 <= paths[i][j].length <= 10
  • 1 <= sum(paths[i][j].length) <= 2 * 10^5
  • path[i][j] 由小写英文字母组成
  • 没有两条路径指向同一个文件夹
  • 对于不在根级别的任何文件夹，其父文件夹也会在输入中

解题思路

这是一个复杂的字符串和哈希问题，需要识别和删除具有相同子结构的文件夹。解决思路如下：

算法步骤：

  1. 构建字典树（Trie）：首先根据路径数组构建一个字典树，每个节点代表一个文件夹，子节点集合代表该文件夹下的直接子文件夹。

  2. 计算子树哈希：从叶子节点开始，向上计算每个节点的子树结构哈希值。对于每个节点，将其所有子节点的名称和对应的哈希值组合起来计算哈希。

  3. 标记重复结构：使用哈希表记录每种子树结构的出现次数。如果某种结构出现多次，则标记所有具有该结构的节点为待删除。

  4. 收集结果：遍历字典树，跳过被标记为删除的节点，收集剩余的有效路径。

关键技巧：

  • 使用后序遍历确保子节点的哈希值在父节点计算前已经确定
  • 只有非空文件夹（有子文件夹的文件夹）才参与重复检测
  • 被标记删除的节点及其所有子节点都要从结果中排除

时间复杂度主要来自于构建Trie树和计算哈希值，空间复杂度取决于Trie树的大小。

代码实现

class Solution {
public:
    struct TrieNode {
        unordered_map<string, TrieNode*> children;
        string hash = "";
        bool toDelete = false;
    };
    
    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
        TrieNode* root = new TrieNode();
        
        // Build trie
        for (auto& path : paths) {
            TrieNode* curr = root;
            for (string& folder : path) {
                if (curr->children.find(folder) == curr->children.end()) {
                    curr->children[folder] = new TrieNode();
                }
                curr = curr->children[folder];
            }
        }
        
        unordered_map<string, vector<TrieNode*>> hashToNodes;
        computeHash(root, hashToNodes);
        
        // Mark duplicates
        for (auto& [hash, nodes] : hashToNodes) {
            if (nodes.size() > 1 && !hash.empty()) {
                for (TrieNode* node : nodes) {
                    node->toDelete = true;
                }
            }
        }
        
        vector<vector<string>> result;
        vector<string> path;
        collectPaths(root, path, result);
        return result;
    }
    
private:
    string computeHash(TrieNode* node, unordered_map<string, vector<TrieNode*>>& hashToNodes) {
        if (node->children.empty()) {
            return "";
        }
        
        vector<string> childHashes;
        for (auto& [name, child] : node->children) {
            string childHash = computeHash(child, hashToNodes);
            childHashes.push_back("(" + name + ":" + childHash + ")");
        }
        
        sort(childHashes.begin(), childHashes.end());
        node->hash = "";
        for (string& ch : childHashes) {
            node->hash += ch;
        }
        
        hashToNodes[node->hash].push_back(node);
        return node->hash;
    }
    
    void collectPaths(TrieNode* node, vector<string>& path, vector<vector<string>>& result) {
        if (node->toDelete) return;
        
        if (!path.empty()) {
            result.push_back(path);
        }
        
        for (auto& [name, child] : node->children) {
            if (!child->toDelete) {
                path.push_back(name);
                collectPaths(child, path, result);
                path.pop_back();
            }
        }
    }
};

class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.hash_val = ""
                self.to_delete = False
        
        root = TrieNode()
        
        # Build trie
        for path in paths:
            curr = root
            for folder in path:
                if folder not in curr.children:
                    curr.children[folder] = TrieNode()
                curr = curr.children[folder]
        
        def compute_hash(node):
            if not node.children:
                return ""
            
            child_hashes = []
            for name, child in node.children.items():
                child_hash = compute_hash(child)
                child_hashes.append(f"({name}:{child_hash})")
            
            child_hashes.sort()
            node.hash_val = "".join(child_hashes)
            hash_to_nodes[node.hash_val].append(node)
            return node.hash_val
        
        hash_to_nodes = defaultdict(list)
        compute_hash(root)
        
        # Mark duplicates
        for hash_val, nodes in hash_to_nodes.items():
            if len(nodes) > 1 and hash_val:
                for node in nodes:
                    node.to_delete = True
        
        def collect_paths(node, path):
            if node.to_delete:
                return
            
            if path:
                result.append(path[:])
            
            for name, child in node.children.items():
                if not child.to_delete:
                    path.append(name)
                    collect_paths(child, path)
                    path.pop()
        
        result = []
        collect_paths(root, [])
        return result

public class Solution {
    public class TrieNode {
        public Dictionary<string, TrieNode> Children = new Dictionary<string, TrieNode>();
        public string Hash = "";
        public bool ToDelete = false;
    }
    
    public IList<IList<string>> DeleteDuplicateFolder(IList<IList<string>> paths) {
        TrieNode root = new TrieNode();
        
        // Build trie
        foreach (var path in paths) {
            TrieNode curr = root;
            foreach (string folder in path) {
                if (!curr.Children.ContainsKey(folder)) {
                    curr.Children[folder] = new TrieNode();
                }
                curr = curr.Children[folder];
            }
        }
        
        Dictionary<string, List<TrieNode>> hashToNodes = new Dictionary<string, List<TrieNode>>();
        ComputeHash(root, hashToNodes);
        
        // Mark duplicates
        foreach (var kvp in hashToNodes) {
            if (kvp.Value.Count > 1 && !string.IsNullOrEmpty(kvp.Key)) {
                foreach (TrieNode node in kvp.Value) {
                    node.ToDelete = true;
                }
            }
        }
        
        IList<IList<string>> result = new List<IList<string>>();
        List<string> path = new List<string>();
        CollectPaths(root, path, result);
        return result;
    }
    
    private string ComputeHash(TrieNode node, Dictionary<string, List<TrieNode>> hashToNodes) {
        if (node.Children.Count == 0) {
            return "";
        }
        
        List<string> childHashes = new List<string>();
        foreach (var kvp in node.Children) {
            string childHash = ComputeHash(kvp.Value, hashToNodes);
            childHashes.Add($"({kvp.Key}:{childHash})");
        }
        
        childHashes.Sort();
        node.Hash = string.Join("", childHashes);
        
        if (!hashToNodes.ContainsKey(node.Hash)) {
            hashToNodes[node.Hash] = new List<TrieNode>();
        }
        hashToNodes[node.Hash].Add(node);
        
        return node.Hash;
    }
    
    private void CollectPaths(TrieNode node, List<string> path, IList<IList<string>> result) {
        if (node.ToDelete) return;
        
        if (path.Count > 0) {
            result.Add(new List<string>(path));
        }
        
        foreach (var kvp in node.Children) {
            if (!kvp.Value.ToDelete) {
                path.Add(kvp.Key);
                CollectPaths(kvp.Value, path, result);
                path.RemoveAt(path.Count - 1);
            }
        }
    }
}

/**
 * @param {string[][]} paths
 * @return {string[][]}
 */
var deleteDuplicateFolder = function(paths) {
    class TrieNode {
        constructor() {
            this.children = new Map();
            this.deleted = false;
        }
    }
    
    const root = new TrieNode();
    
    // Build trie
    for (const path of paths) {
        let node = root;
        for (const folder of path) {
            if (!node.children.has(folder)) {
                node.children.set(folder, new TrieNode());
            }
            node = node.children.get(folder);
        }
    }
    
    // Generate signatures and mark duplicates
    const signatures = new Map();
    
    function getSignature(node) {
        if (node.children.size === 0) {
            return "";
        }
        
        const childSigs = [];
        for (const [name, child] of node.children) {
            const childSig = getSignature(child);
            childSigs.push(`${name}(${childSig})`);
        }
        
        childSigs.sort();
        const signature = childSigs.join("");
        
        if (!signatures.has(signature)) {
            signatures.set(signature, []);
        }
        signatures.get(signature).push(node);
        
        return signature;
    }
    
    getSignature(root);
    
    // Mark nodes for deletion
    for (const [sig, nodes] of signatures) {
        if (nodes.length > 1 && sig !== "") {
            for (const node of nodes) {
                markDeleted(node);
            }
        }
    }
    
    function markDeleted(node) {
        node.deleted = true;
        for (const child of node.children.values()) {
            markDeleted(child);
        }
    }
    
    // Collect remaining paths
    const result = [];
    
    function dfs(node, path) {
        for (const [name, child] of node.children) {
            if (!child.deleted) {
                const newPath = [...path, name];
                result.push(newPath);
                dfs(child, newPath);
            }
        }
    }
    
    dfs(root, []);
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度表达式说明
时间复杂度O(N × M + K × log K)N为路径总数，M为平均路径长度，K为节点总数
空间复杂度O(K × H)K为节点

相关题目