Trie+ dfs+ serialization
Approach\n\n Use trieNode to create the trie of folder structure.\n Then do dfs on trie and serialize subtrees as strings, then add nodes which has the same ser
**Approach**\n\n* Use `trieNode` to create the trie of folder structure.\n* Then do dfs on trie and serialize subtrees as strings, then add nodes which has the same serialize string into a dictionary and increment it\'s count,\n* Traverse the trie, if nodes has the same serialize(hash) string and count>1, then it\'s duplicated subtree, we delete those from trie.\n* Traverse the whole trie again to get all the paths.\n\n\n\n```\nfunc deleteDuplicateFolder(paths [][]string) [][]string {\n\ttrie := Trie{&trieNode{make(map[string]*trieNode), ""}, make(map[string]int)}\n\tfor _, path := range paths {\n\t\ttrie.Insert(path)\n\t}\n\ttrie.Serialize()\n\ttrie.DeleteDuplicate()\n\treturn trie.Traverse()\n\n}\n\ntype Trie struct {\n\troot *trieNode\n\tmp   map[string]int\n}\ntype trieNode struct {\n\tchild map[string]*trieNode\n\thash  string\n}\n\nfunc newTrieNode() *trieNode {\n\treturn &trieNode{make(map[string]*trieNode), ""}\n}\n\nfunc (t *Trie) DeleteDuplicate() {\n\tvar dfs func(*trieNode)\n\tdfs = func(root *trieNode) {\n\t\tif len(root.child) == 0 {\n\t\t\treturn\n\t\t}\n\t\tfor k := range root.child {\n\t\t\tif v, ok := t.mp[root.child[k].hash]; ok && v > 1 {\n\t\t\t\tdelete(root.child, k)\n\t\t\t} else {\n\t\t\t\tdfs(root.child[k])\n\t\t\t}\n\t\t}\n\t}\n\tdfs(t.root)\n}\n\nfunc (t *Trie) Insert(path []string) {\n\troot := t.root\n\tfor _, p := range path {\n\t\tif root.child[p] == nil {\n\t\t\troot.child[p] = newTrieNode()\n\t\t}\n\t\troot = root.child[p]\n\t}\n}\n\nfunc (t Trie) Serialize() {\n\tvar dfs func(*trieNode, string) string\n\tdfs = func(root *trieNode, n string) string {\n\t\tif len(root.child) == 0 {\n\t\t\treturn n\n\t\t}\n\t\thash := ""\n\t\tvar children []string\n\t\tfor k := range root.child {\n\t\t\tchildren = append(children, k)\n\t\t}\n\t\tsort.Strings(children)\n\t\tfor _, k := range children {\n            hash += fmt.Sprintf("(%s)",dfs(root.child[k], k))\n\t\t}\n\t\troot.hash = hash\n\t\tt.mp[hash]++\n\t\tfmt.Println("root: ", n, "=", root.hash)\n\t\treturn n + "/" + hash\n\t}\n\tt.root.hash = dfs(t.root, "")\n}\n\nfunc (t Trie) Traverse() [][]string {\n\tpaths := make([][]string, 0)\n\tvar dfs func(root *trieNode, currPath []string)\n\tdfs = func(root *trieNode, currPath []string) {\n\t\tif len(root.child) == 0 {\n\t\t\tif len(currPath) > 0 {\n\t\t\t\tpaths = append(paths, append([]string{}, currPath...))\n\t\t\t}\n\t\t\treturn\n\t\t}\n\t\tif len(currPath) > 0 {\n\t\t\tpaths = append(paths, append([]string{}, currPath...))\n\t\t}\n\t\tfor k, _ := range root.child {\n\t\t\tdfs(root.child[k], append(currPath, k))\n\t\t}\n\t}\n\n\tdfs(t.root, []string{})\n\treturn paths\n}\n```
['Depth-First Search', 'Trie', 'Go']