[Golang] Trie + DFS + Simple Hashing
go\ntype TrieNode struct {\n  hash string\n  children map[string]*TrieNode\n}\n\nfunc deleteDuplicateFolder(paths [][]string) [][]string {\n  root := &TrieNode{
```go\ntype TrieNode struct {\n  hash string\n  children map[string]*TrieNode\n}\n\nfunc deleteDuplicateFolder(paths [][]string) [][]string {\n  root := &TrieNode{children: make(map[string]*TrieNode)}\n  for _, path := range paths {\n    insert(root, path)\n  }\n  // Now we\'re going to do a DFS to compute hash for each node\n  // As part of that we\'re also going to count the occurrences of each hash key\n  hashCounts := make(map[string]int)\n  dfs(root, hashCounts)\n  var res [][]string\n  render(root, hashCounts, nil, &res)\n  return res\n}\n\nfunc render(root *TrieNode, hashCounts map[string]int, curr []string, res *[][]string) {\n  if len(curr) > 0 {\n    // Make a copy so when we go down the tree the slice doesn\'t get modified in \n    // the final result.\n    curr2 := make([]string, len(curr))\n    copy(curr2, curr)\n    *res = append(*res, curr2)\n  }\n  for key, child := range root.children {\n    if hashCounts[child.hash] > 1 { // duplicate; discard the entire subtree here\n      continue\n    }\n    curr = append(curr, key)\n    render(child, hashCounts, curr, res)\n    curr = curr[:len(curr)-1]\n  }\n}\n\nfunc dfs(root *TrieNode, hashCounts map[string]int) {\n  // We\'re going to process the keys in sorted order\n  // We compute hash simply using \'(\' and \')\'\n  // For example x(y)(z) is the hash of a directory that contains\n  // x and x contains y and z as child directories.\n  var h string\n  for _, key := range sortedKeys(root.children) {\n    dfs(root.children[key], hashCounts)\n    var currHash string\n    if root.children[key].hash != "" {\n      currHash = fmt.Sprintf("%s(%s)", key, root.children[key].hash)\n    } else {\n      currHash = fmt.Sprintf("%s", key)\n    }\n    h += currHash\n  }\n  if h != "" {\n    hashCounts[h]++\n  }\n  root.hash = h\n}\n\nfunc sortedKeys(m map[string]*TrieNode) []string {\n  keys := make([]string, 0, len(m))\n  for k := range m {\n    keys = append(keys, k)\n  }\n  sort.Strings(keys)\n  return keys\n}\n\nfunc insert(root *TrieNode, path []string) {\n  curr := root\n  for i := 0; i < len(path); i++ {\n    child := curr.children[path[i]]\n    if child == nil {\n      child = &TrieNode{children: make(map[string]*TrieNode)}\n      curr.children[path[i]] = child\n    }\n    curr = child\n  }\n}\n```
['Depth-First Search', 'Trie', 'Go']