# https://leetcode.com/problems/remove-sub-folders-from-the-filesystem
from typing import List
import copy

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        def push(trie, words, index):
            if index >= len(words):
                trie['end'] = True
                return
            if words[index] not in trie:
                trie[words[index]] = {}
            return push(trie[words[index]], words, index + 1)
        def pop(trie, curr, ret):
            if trie == None:
                return 
            if 'end' in trie:
                ret.append('/' + '/'.join(curr))
                return
            for k, v in trie.items():
                cur = copy.deepcopy(curr)
                cur.append(k)
                pop(v, cur, ret)
        for each in folder:
            words = each.split('/')
            push(trie, words[1:], 0)
        ret = []
        pop(trie, [], ret)
        return ret