1233. Remove Sub-Folders from the Filesystem

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word.split("/"):
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root

        # Check for all parents until last folder
        for char in word.split("/")[:-1]:
            node = node.children[char]
            if node.is_end_of_word:
                return False

        return True

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for e in folder:
            trie.insert(e)

        ans = []
        for e in folder:
            if trie.search(e):
                ans.append(e)

        return ans