上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
}
};
java 解法, 执行用时: 196 ms, 内存消耗: 63.7 MB, 提交时间: 2023-06-13 14:15:00
class Trie
{
String ss;
Map<String, Trie> children;
Trie()
{
this.ss = "";
this.children = new HashMap<>();
}
//------------ 向trie树中插入path
public void insert_path(List<String> path)
{
Trie root = this;
for (String p : path)
{
if (root.children.containsKey(p) == false)
root.children.put(p, new Trie());
root = root.children.get(p);
}
}
}
class Solution
{
// Trie T = new Trie();
// Map<String, Integer> ss_cnt = new HashMap<>();
// List<List<String>> res = new ArrayList<>();
// List<String> path = new ArrayList<>(); //回溯过程中的路径
Trie T;
Map<String, Integer> ss_cnt;
List<List<String>> res;
List<String> path;
public List<List<String>> deleteDuplicateFolder(List<List<String>> paths)
{
this.T = new Trie();
this.ss_cnt = new HashMap<>();
this.res = new ArrayList<>();
this.path = new ArrayList<>();
//---------- （1）将所有的path都插入trie树T中
for (List<String> path: paths)
T.insert_path(path);
//--------- （2）在T上进行dfs_LRN，求得每个结点对应的ss
dfs_LRN_get_trieNode_ss(this.T);
//-------- path可能会很长。回溯算法求res
backtrace_get_res(this.T);
return this.res;
}
//------ dfs_LRN 获得每个trie_node的ss
public void dfs_LRN_get_trieNode_ss(Trie node)
{
if (node.children.size() == 0)
return ;
List<String> ss = new ArrayList<>();
for (Map.Entry<String, Trie> kv : node.children.entrySet())
{
String child = kv.getKey(); Trie child_trie = kv.getValue();
dfs_LRN_get_trieNode_ss(child_trie);
ss.add(child + "(" + child_trie.ss + ")");
}
Collections.sort(ss);
for (String s: ss)
node.ss += s;
// System.out.println(node.ss);
ss_cnt.put(node.ss, ss_cnt.getOrDefault(node.ss, 0) + 1);
}
//----- 回溯算法，求res
public void backtrace_get_res(Trie node)
{
if (ss_cnt.getOrDefault(node.ss, 0) >= 2)
return ;
if (path.size() > 0)
{
// List<String> tmp = new ArrayList<>();
// for (String p: path)
// tmp.add(p);
// res.add(tmp);
res.add(new ArrayList<>(path));
}
for (Map.Entry<String, Trie> kv : node.children.entrySet())
{
String child = kv.getKey(); Trie child_trie = kv.getValue();
path.add(child);
backtrace_get_res(child_trie);
path.remove(path.size() - 1);
}
}
}
python3 解法, 执行用时: 408 ms, 内存消耗: 43.6 MB, 提交时间: 2023-06-13 14:14:02
class Trie:
# 当前节点结构的序列化表示
serial: str = ""
# 当前节点的子节点
children: dict
def __init__(self):
self.children = dict()
class Solution:
def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
# 根节点
root = Trie()
for path in paths:
cur = root
for node in path:
if node not in cur.children:
cur.children[node] = Trie()
cur = cur.children[node]
# 哈希表记录每一种序列化表示的出现次数
freq = Counter()
# 基于深度优先搜索的后序遍历，计算每一个节点结构的序列化表示
def construct(node: Trie) -> None:
# 如果是叶节点，那么序列化表示为空字符串，无需进行任何操作
if not node.children:
return
v = list()
# 如果不是叶节点，需要先计算子节点结构的序列化表示
for folder, child in node.children.items():
construct(child)
v.append(folder + "(" + child.serial + ")")
# 防止顺序的问题，需要进行排序
v.sort()
node.serial = "".join(v)
# 计入哈希表
freq[node.serial] += 1
construct(root)
ans = list()
# 记录根节点到当前节点的路径
path = list()
def operate(node: Trie) -> None:
# 如果序列化表示在哈希表中出现了超过 1 次，就需要删除
if freq[node.serial] > 1:
return
# 否则将路径加入答案
if path:
ans.append(path[:])
for folder, child in node.children.items():
path.append(folder)
operate(child)
path.pop()
operate(root)
return ans
golang 解法, 执行用时: 420 ms, 内存消耗: 16 MB, 提交时间: 2023-06-13 14:13:22
// 字典树 + 括号表示法 + 哈希表
type folder struct {
son map[string]*folder
val string // 文件夹名称
del bool // 删除标记
}
func deleteDuplicateFolder(paths [][]string) (ans [][]string) {
root := &folder{}
for _, path := range paths {
// 将 path 加入字典树
f := root
for _, s := range path {
if f.son == nil {
f.son = map[string]*folder{}
}
if f.son[s] == nil {
f.son[s] = &folder{}
}
f = f.son[s]
f.val = s
}
}
folders := map[string][]*folder{} // 存储括号表达式及其对应的文件夹节点列表
var dfs func(*folder) string
dfs = func(f *folder) string {
if f.son == nil {
return "(" + f.val + ")"
}
expr := make([]string, 0, len(f.son))
for _, son := range f.son {
expr = append(expr, dfs(son))
}
sort.Strings(expr)
subTreeExpr := strings.Join(expr, "") // 按字典序拼接所有子树
folders[subTreeExpr] = append(folders[subTreeExpr], f)
return "(" + f.val + subTreeExpr + ")"
}
dfs(root)
for _, fs := range folders {
if len(fs) > 1 { // 将括号表达式对应的节点个数大于 1 的节点全部删除
for _, f := range fs {
f.del = true
}
}
}
// 再次 DFS 这颗字典树，仅访问未被删除的节点，并将路径记录到答案中
path := []string{}
var dfs2 func(*folder)
dfs2 = func(f *folder) {
if f.del {
return
}
path = append(path, f.val)
ans = append(ans, append([]string(nil), path...))
for _, son := range f.son {
dfs2(son)
}
path = path[:len(path)-1]
}
for _, son := range root.son {
dfs2(son)
}
return
}
