1948. 删除系统中的重复文件夹

1948. 删除系统中的重复文件夹 - 力扣（LeetCode）

class TrieNode:__slots__ = 'son','name','deleted'def __init__(self):self.son = {}self.name = ''self.deleted = False
class Solution:def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:root = TrieNode()for path in paths:cur = rootfor s in path:if s not in cur.son:cur.son[s] = TrieNode()cur = cur.son[s]cur.name = sexpr_to_node = {}def gen_expr(node: TrieNode)->str:if not node.son:return node.nameexpr = sorted('(' + gen_expr(son) + ')' for son in node.son.values())sub_tree_expr = ''.join(expr)if sub_tree_expr in expr_to_node:expr_to_node[sub_tree_expr].deleted = Truenode.deleted = Trueelse:expr_to_node[sub_tree_expr] = nodereturn node.name + sub_tree_exprfor son in root.son.values():gen_expr(son)ans = []path = []def dfs(node:TrieNode)->None:if node.deleted:returnpath.append(node.name)ans.append(path.copy())for child in node.son.values():dfs(child)path.pop()for son in root.son.values():dfs(son)return ans