题面解释:

在某文件系统中，存在一些重复的文件夹，重复文件夹的定义为：如果两个或多个文件夹包含相同的非空子文件夹，并且这些子文件夹的结构也相同，则这些文件夹被认为是重复的。输入由多行组成，第一行是文件夹路径的数量 $n$，接下来的 $n$ 行是各个文件夹的路径。路径以 "/" 开头和结尾，中间每层由 "/" 分隔。输出所有重复文件夹的父路径，按字典升序排列；如果不存在重复的文件夹，则输出“NotFound”。

思路:序列化唯一表示树

问题本质为：构建出文件目录树后，询问有多少个子树，忽略根节点以后，他们的子树完全相等。

一个朴素的思路是枚举所有子树，然后进行递归check。

但是这个方法的时间复杂度过高$O(n^3)$，需要优化，考虑对每个子树进行一个序列化表示 + 哈希。然后再枚举子树 + 哈希值判定。

伪代码如下

# 定义函数 is_the_same，用于判断两个子树 node1 和 node2 是否相同
def is_the_same(node1, node2):
    # 对 node1 和 node2 的子节点分别进行排序，确保子节点的顺序一致
    sorted_son_node1 = sorted(node1.son)  # 将 node1 的子节点按名称排序
    sorted_son_node2 = sorted(node2.son)  # 将 node2 的子节点按名称排序
    
    # 如果两个节点的子节点数量不同，直接返回 False，说明不是相同子树
    if len(sorted_son_node1) != len(sorted_son_node2):
        return False
    
    # 逐个比较每一对排序后的子节点
    for i in range(len(sorted_son_node1)):
        # 如果当前子节点的名称不同，返回 False，说明子树不同
        if sorted_son_node1[i].name != sorted_son_node2[i].name:
            return False
        
        # 递归比较当前子节点的子树是否相同，如果有任意一个子树不相同，返回 False
        if is_the_same(sorted_son_node1[i], sorted_son_node2[i]) == False:
            return False
    
    # 如果所有子节点都相同且对应子树也相同，返回 True，表示两棵树相同
    return True

# 双重循环枚举树中所有节点的组合
for i in node:
    for j in node:
        # 调用 is_the_same 函数比较节点 i 和 j 的子树是否相同
        if not is_the_same(i, j):
            record(i)
            record(j)

return record.set()

题解

本题的核心在于构建一个文件目录树，并找出其中重复的子树。重复子树的定义为：如果某个子树结构完全相同，并且含有相同的子文件夹（忽略根节点），则这些子树被认为是重复的。为了有效检测这些重复的子树，我们采用以下步骤：

1. 树节点定义：使用 TreeNode 结构体来表示每个文件夹，存储子文件夹的信息，包括路径和是否为重复子树的标志。

2. 序列化树结构：通过递归遍历树的方式，将每个子树序列化为一个唯一的字符串表示。这一过程中，我们将子节点的序列化结果排序并组合，以确保相同结构的子树能生成相同的字符串。

3. 重复检测：使用哈希表存储已序列化的子树。如果再次遇到相同的序列化结果，则标记这些树节点为重复的。

4. 结果收集：遍历整棵树，找到所有标记为重复的子树，并将其父节点路径收集到结果中。

5. 输出结果：对结果进行排序，并输出每个重复子树的父路径。如果没有重复子树，则输出“NotFound”。

具体步骤:

1.构建文件目录树：通过读取输入的路径信息，将其分层解析并逐级添加到树节点中，每个路径的层级信息通过 / 分割，并逐级构建树节点。

2.子树的序列化表示：对于每个节点，通过递归的方式序列化其所有子节点，将该节点的结构和内容唯一表示成一个字符串。子节点的序列化结果会拼接并排序，保证相同结构的子树在不同位置也能得到相同的序列化字符串。

3.利用哈希表检测重复子树：每棵子树的序列化字符串作为哈希表的键值，若相同的序列化字符串已经出现，则将该子树标记为重复，并记录其父节点路径。

4.输出所有重复子树的父节点路径：遍历整棵树，查找被标记为重复的子树，记录其父节点路径，若没有重复子树则输出 "NotFound"，否则按字典序输出所有父节点路径。

代码

cpp

#include <iostream>   // 用于输入输出
#include <unordered_map>  // 哈希表
#include <vector>     // 动态数组
#include <string>     // 字符串操作
#include <algorithm>  // sort排序函数

using namespace std;

// 树节点结构体
struct TreeNode {
    unordered_map<string, TreeNode*> children; // 存储子节点
    string path;   // 当前节点路径
    bool isDuplicate;  // 标记是否为重复子树

    // 构造函数初始化
    TreeNode() : isDuplicate(false) {}
};

// 存储序列化子树的哈希表，用于检测重复
unordered_map<string, TreeNode*> duplicates;  

// 序列化树结构，将其转为唯一字符串表示
string serialize(TreeNode* root) {
    if (root->children.empty()) return "#";  // 如果没有子节点，返回 "#"

    vector<string> paths; // 存储所有子节点的序列化结果

    // 遍历所有子节点并进行序列化
    for (const auto& child : root->children) {
        paths.push_back(child.first + "(" + serialize(child.second) + ")");
    }

    sort(paths.begin(), paths.end());  // 排序确保结构唯一性

    string serialized; // 存储最终的序列化字符串
    for (const auto& p : paths) {
        serialized += p;  // 组合所有子节点的序列化字符串
    }

    // 检测是否已有相同结构的子树
    if (duplicates.count(serialized)) {
        duplicates[serialized]->isDuplicate = true;  // 标记为重复
        root->isDuplicate = true;  // 当前节点也标记为重复
    } else {
        duplicates[serialized] = root;  // 存储序列化结果
    }
    return serialized; // 返回序列化字符串
}

// 查找所有重复子树的父节点路径
void findParentDuplicates(TreeNode* root, vector<string>& result) {
    if (root->isDuplicate) {  // 如果当前节点是重复子树，加入结果
        result.push_back(root->path); // 添加父节点路径到结果
        return;
    }
    // 递归检查所有子节点
    for (const auto& child : root->children) {
        findParentDuplicates(child.second, result);
    }
}

int main() {
    int n;
    cin >> n;  // 输入路径数量

    TreeNode* root = new TreeNode();  // 初始化根节点

    // 构建树结构
    for (int i = 0; i < n; ++i) {
        string path;
        cin >> path;  // 输入每条路径
        TreeNode* curr = root; // 当前节点指向根节点
        size_t pos = 1; // 路径的开始位置，跳过第一个 '/'
        
        // 根据路径层级逐级创建树节点
        while (pos < path.size()) {
            size_t nextPos = path.find('/', pos); // 找到下一个 '/'
            string dir = path.substr(pos, nextPos - pos); // 提取当前文件夹名称
            if (!curr->children.count(dir)) {  // 如果节点不存在，则创建
                curr->children[dir] = new TreeNode();
                curr->children[dir]->path = path.substr(0, 
                                nextPos == string::npos ? path.size() : nextPos);
            }
            curr = curr->children[dir];  // 进入下一层节点
            pos = nextPos == string::npos ? path.size() : nextPos + 1; // 更新位置
        }
    }

    serialize(root);  // 序列化整棵树
    vector<string> result; // 存储重复子树的父节点路径
    findParentDuplicates(root, result);  // 查找重复子树的父节点

    sort(result.begin(), result.end());  // 结果排序
    if (result.empty()) {
        cout << "NotFound" << endl;  // 无重复子树
    } else {
        for (const auto& r : result) {
            cout << r << "/" << endl;  // 输出重复子树的父节点路径
        }
    }

    return 0; // 程序结束
}

python

# 导入 defaultdict 来构建树形结构
from collections import defaultdict

# 读取输入路径的数量
n = int(input())

# 定义一个 Node 类表示文件夹节点
class Node:
    def __init__(self):
        self.name = ""  # 当前文件夹的名称
        # to 表示从当前节点到其子节点的字典，键是文件夹名，值是 Node 对象，子文件夹存储于此
        self.to = defaultdict(Node)
        # is_duplicate 标志当前节点是否是重复文件夹
        self.is_duplicate = False

# 初始化根节点，根目录用 "root" 作为名称
root = Node()
root.name = "root"

# 创建一个字典 book，用于存储子树结构的序列化字符串
book = defaultdict(str)

# 构建文件夹结构树
for _ in range(n):
    # 读取路径并分割，去掉前后的空元素 '/'，只保留中间的部分
    paths = input().split("/")
    paths = paths[1:-1]  # 删除第一个空元素和最后一个空元素
    now = root  # 从根节点开始插入文件夹路径
    for path in paths:
        # 如果当前子文件夹不存在，创建新的节点
        if path not in now.to:
            now.to[path] = Node()  # 新节点
            now.to[path].name = path  # 设置新节点的名字
        # 继续深入到子文件夹
        now = now.to[path]

# 序列化文件夹树结构函数，用于比较文件夹结构是否相同
def serialize(root):
    ser_arr = []  # 存储当前节点下所有子树的序列化字符串
    # 遍历当前节点的子节点
    for v in root.to:
        # 递归获取子节点的序列化字符串
        ser_arr.append(serialize(root.to[v]))
    ser_arr.sort()  # 将子树按字典序排序，保证同一结构的文件夹顺序一致
    ser_str = ""  # 初始化序列化字符串
    # 拼接所有子文件夹的序列化结果
    for s in ser_arr:
        ser_str += s

    # 如果当前节点有子文件夹
    if ser_str != "":
        # 检查当前序列化结果是否已经存在
        if ser_str in book:
            # 如果存在相同的子树结构，标记该节点及其之前记录的节点为重复
            book[ser_str].is_duplicate = True
            root.is_duplicate = True
        else:
            # 如果不存在相同的子树结构，记录当前序列化结果
            book[ser_str] = root
    # 返回当前节点的序列化形式 "文件夹名称(子文件夹序列化)"
    return root.name + "(" + ser_str + ")"

# 保存重复文件夹路径的结果列表
res = []

# 查找并标记重复文件夹的函数
def find_duplicate(root, path):
    global res
    # 如果不是根目录，将当前路径加入 path
    if root.name != "root":
        path += root.name + "/"
    # 如果当前节点是重复文件夹，保存路径并返回
    if root.is_duplicate:
        res.append(path)
        return
    # 递归检查当前节点的子文件夹
    for v in root.to:
        find_duplicate(root.to[v], path)

# 序列化整个文件夹树，从根开始
serialize(root)
# 从根节点开始查找所有重复的文件夹，并记录其路径
find_duplicate(root, "/")

# 按字典序排序结果
res.sort()

# 如果找到重复文件夹，按行输出结果，否则输出 "NotFound"
if len(res) != 0:
    print("\n".join(res))
else:
    print("NotFound")

java

import java.util.*;

// 用于表示树的节点
class TreeNode {
    Map<String, TreeNode> children; // 存储子节点
    String path; // 当前节点路径
    boolean isDuplicate; // 标记是否为重复子树

    TreeNode() {
        children = new HashMap<>();
        isDuplicate = false;
    }
}
public class Main{
    
        // 存储序列化子树，检测重复
        static Map<String, TreeNode> duplicates = new HashMap<>();

        // 序列化树结构，将其转为唯一字符串表示
        public static String serialize(TreeNode root) {
            if (root.children.isEmpty()) return "#"; // 如果没有子节点，返回 "#"

            List<String> paths = new ArrayList<>();
            // 遍历所有子节点
            for (Map.Entry<String, TreeNode> child : root.children.entrySet()) {
                paths.add(child.getKey() + "(" + serialize(child.getValue()) + ")");
            }
            Collections.sort(paths); // 排序确保结构唯一性

            StringBuilder serialized = new StringBuilder();
            for (String p : paths) {
                serialized.append(p); // 组合所有子节点的序列化字符串
            }

            // 检测是否已有相同结构的子树
            if (duplicates.containsKey(serialized.toString())) {
                duplicates.get(serialized.toString()).isDuplicate = true; // 标记为重复
                root.isDuplicate = true;
            } else {
                duplicates.put(serialized.toString(), root); // 存储序列化结果
            }
            return serialized.toString();
        }

        // 查找所有重复子树的父节点路径
        public static void findParentDuplicates(TreeNode root, List<String> result) {
            if (root.isDuplicate) { // 如果是重复子树，加入结果
                result.add(root.path);
                return;
            }
            // 递归检查所有子节点
            for (TreeNode child : root.children.values()) {
                findParentDuplicates(child, result);
            }
        }

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt(); // 输入路径数量

            TreeNode root = new TreeNode(); // 初始化根节点

            // 构建树结构
            for (int i = 0; i < n; ++i) {
                String path = scanner.next(); // 输入每条路径
                TreeNode curr = root;
                int pos = 1;

                // 根据路径层级逐级创建树节点
                while (pos < path.length()) {
                    int nextPos = path.indexOf('/', pos);
                    String dir = path.substring(pos, nextPos == -1 ? path.length() : nextPos);
                    if (!curr.children.containsKey(dir)) { // 如果节点不存在，则创建
                        curr.children.put(dir, new TreeNode());
                        curr.children.get(dir).path = path.substring(0, nextPos == -1 ? path.length() : nextPos);
                    }
                    curr = curr.children.get(dir); // 进入下一层节点
                    pos = nextPos == -1 ? path.length() : nextPos + 1;
                }
            }


            String serializedTree = serialize(root); // 序列化整棵树
            List<String> result = new ArrayList<>();
             findParentDuplicates(root, result); // 查找重复子树的父节点

            Collections.sort(result); // 结果排序

            if (result.isEmpty()) {
                System.out.println("NotFound"); // 无重复子树
            } else {
                for (String r : result) {
                    System.out.println(r + "/"); // 输出重复子树的父节点路径
                }
            }
            scanner.close();
        }

}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

某文件系统中存在一些重复的文件夹，需要找出来并删除。

重复文件夹的定义：如果存在两个（或以上）的文件夹，包含非空且相同的子文件夹，且子文件夹的结构也相同，则认为这些文件夹是重复文件夹。重复文件夹可以属于不同的文件层级。

例如，存在如下文件夹结构：

$/a/x/y/$

$/a/z/$

$/b/x/y/$

$/b/z/$

则文件夹 $/a/$ 和 $/b/$ 为重复文件夹。

如果再新增一个 $/b/w/$ 文件夹，则 $/a/$ 和 $/b/$ 不再是重复文件夹，但 $/a/x/$ 和 $/b/x/$ 仍为重复文件夹，$/a/z/$ 和 $/b/z/$ 不算作重复文件夹，因为 $z$ 目录下是空的。

给你一组数组 $paths$ ，表示系统中所有存在的文件夹结构，请找出所有的重复文件夹。

如果重复文件夹之间存在父子关系，只返回父文件夹即可（即如果 $/a/$ 和 $/a/x/$ 均为重复文件夹，只返回 $/a/$ 即可），并按字典序返回。

如果不存在重复目录，返回字符串 $NotFound$。

输入描述

输入由多行组成，第一行表示 $paths$ 中的元素个数 $n$，第$2$~$n+1$行为 $n$ 个路径名。

每个路径以 "/" 开头和结尾，中间每个层级以 "/" 分隔。

$1≤paths.length≤2×10^4$

$paths$ 中每个路径的层数 $≤500$

$1≤$ 每层文件夹名称的长度 $≤10$

$paths[i]$由小写英文字母和 / 组成，

$paths$ 中的路径不存在重复。

输出描述

返回所有重复文件夹的路径名，每行一个，路径的格式与输入格式一致，各个路径的顺序按字母升序排列。

样例1

输入

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

输出

/a/
/b/

样例2

输入

5
/a/x/y/
/a/z/
/b/x/y/
/b/z/
/b/w/

输出

/a/x/
/b/x/

样例3

输入

4
/a/x/y/
/a/z/
/b/z/
/b/w/

输出

NotFound

样例4 (小明补充的，实际没有)

输入

11
/a/
/a/b/
/a/d/
/a/b/a/
/a/b/c/
/a/c/a/
/a/c/c/
/a/d/f/
/a/d/d/
/a/e/f/
/a/e/d/

输出

/a/b/
/a/c/
/a/d/
/a/e/