<p>Given a list of folders <code>folder</code>, return <em>the folders after removing all <strong>sub-folders</strong> in those folders</em>. You may return the answer in <strong>any order</strong>.</p>

<p>If a <code>folder[i]</code> is located within another <code>folder[j]</code>, it is called a <strong>sub-folder</strong> of it.</p>

<p>The format of a path is one or more concatenated strings of the form: <code>&#39;/&#39;</code> followed by one or more lowercase English letters.</p>

<ul>
	<li>For example, <code>&quot;/leetcode&quot;</code> and <code>&quot;/leetcode/problems&quot;</code> are valid paths while an empty string and <code>&quot;/&quot;</code> are not.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> folder = [&quot;/a&quot;,&quot;/a/b&quot;,&quot;/c/d&quot;,&quot;/c/d/e&quot;,&quot;/c/f&quot;]
<strong>Output:</strong> [&quot;/a&quot;,&quot;/c/d&quot;,&quot;/c/f&quot;]
<strong>Explanation:</strong> Folders &quot;/a/b&quot; is a subfolder of &quot;/a&quot; and &quot;/c/d/e&quot; is inside of folder &quot;/c/d&quot; in our filesystem.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> folder = [&quot;/a&quot;,&quot;/a/b/c&quot;,&quot;/a/b/d&quot;]
<strong>Output:</strong> [&quot;/a&quot;]
<strong>Explanation:</strong> Folders &quot;/a/b/c&quot; and &quot;/a/b/d&quot; will be removed because they are subfolders of &quot;/a&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> folder = [&quot;/a/b/c&quot;,&quot;/a/b/ca&quot;,&quot;/a/b/d&quot;]
<strong>Output:</strong> [&quot;/a/b/c&quot;,&quot;/a/b/ca&quot;,&quot;/a/b/d&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= folder.length &lt;= 4 * 10<sup>4</sup></code></li>
	<li><code>2 &lt;= folder[i].length &lt;= 100</code></li>
	<li><code>folder[i]</code> contains only lowercase letters and <code>&#39;/&#39;</code>.</li>
	<li><code>folder[i]</code> always starts with the character <code>&#39;/&#39;</code>.</li>
	<li>Each folder name is <strong>unique</strong>.</li>
</ul>

class FolderNode:
    def __init__(self, name):
        self.name = name
        self.isLeaf = False
        self.childrens = {}

    def addNode(self, names):
        if len(names) == 0:
            self.isLeaf = True
        else:
            name = names[0]
            if name not in self.childrens:
                self.childrens[name] = FolderNode(name)
            self.childrens[name].addNode(names[1:])

    def prefix(self):
        if self.isLeaf:
            print('(n)', end=' ')
        else:
            print(end= ' ')
        for name in self.childrens:
            print(name,end='')
            self.childrens[name].prefix()

    def cut(self):
        if self.isLeaf:
            self.childrens = {}
        else:
            for name in self.childrens:
                self.childrens[name].cut()

    def fetchAll(self, path, li):
        if self.isLeaf:
            li.append(path)
        else:
            for name in self.childrens:
                self.childrens[name].fetchAll(path + "/" + name, li)



class Solution:
    def removeSubfolders(self, folder):
        trie = FolderNode('')

        for path in folder:
            names = path.split('/')[1:]
            trie.addNode(names)

        # cut trie by DFS
        trie.cut()

        # get all words by DFS
        answer = []
        trie.fetchAll('', answer)
        return answer

41800