Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.
If a folder[i] is located within another folder[j], it is called a sub-folder of it.
The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.
 
Example 1:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:
Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".

Example 3:
Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

 
Constraints:

1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and '/'
folder[i] always starts with character '/'
Each folder name is unique.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        

Solutions:
class Solution:

	def removeSubfolders(self, folder):
		folders = folder
		folders.sort()
		output = []
		parent = ' '
		for folder in folders:
			if not folder.startswith(parent):
				output.append(folder)
				parent = folder + '/'
		return output


class Trie:

	def __init__(self):
		self.next = {}
		self.end_here = False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:

		def collect(curnode, res, curpath):
			if curnode.end_here:
				res.append('/'.join(curpath))
				return
			for folder in curnode.next:
				curpath.append(folder)
				collect(curnode.next[folder], res, curpath)
				curpath.pop()
		root = Trie()
		for f in folder:
			cur = root
			for seg in f.split('/'):
				if seg not in cur.next:
					cur.next[seg] = Trie()
				cur = cur.next[seg]
			cur.end_here = True
		res = []
		collect(root, res, [])
		return res


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isEnd = False

class Trie:

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

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

	def find(self):

		def dfs(direc, node):
			if node.isEnd:
				answer.append('/' + '/'.join(direc))
				return
			for char in node.children:
				dfs(direc + [char], node.children[char])
		answer = []
		dfs([], self.root)
		return answer

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = Trie()
		for f in folder:
			f = f.split('/')[1:]
			print(f)
			trie.insert(f)
		return trie.find()


class Trie:

	def __init__(self, *words):
		self._end = '_end'
		self.root = {}
		self.insert(*words)

	def insert(self, *words):
		_end = self._end
		root = self.root
		for word in words:
			current_dict = root
			for letter in word:
				current_dict = current_dict.setdefault(letter, {})
			current_dict[_end] = _end
		return root

	def has(self, word):
		trie = self.root
		_end = self._end
		current_dict = trie
		for letter in word:
			if letter not in current_dict:
				return False
			current_dict = current_dict[letter]
		return _end in current_dict

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		if folder:
			folder.sort()
		r = []
		trie = Trie()
		for f in folder:
			names = [x for x in f.split('/') if x.strip()]
			to_insert = True
			for i in range(1, len(names) + 1):
				subfolder = '/'.join(names[:i])
				subfolder = '/' + subfolder if subfolder else subfolder
				if trie.has(subfolder):
					to_insert = False
					break
			if to_insert:
				r.append(f)
				trie.insert(f)
		return r


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		d = {}
		for f in folder:
			names = ''.join(f.split('/'))
			if len(names) > 0:
				d[names] = f
		output = []
		for f in folder:
			names = ''.join(f.split('/')[:-1])
			if not [True for i in range(len(names)) if names[:i + 1] in d]:
				output.append(f)
		return output


class Trie:

	def __init__(self):
		self.root = {}

	def insert(self, word):
		cur = self.root
		for ch in word:
			if ch not in cur:
				cur[ch] = {}
			cur = cur[ch]
		cur['END'] = {}

	def search(self):

		def dfs(node, tmp, res):
			if 'END' in node:
				res.append(''.join(tmp))
			else:
				for ch in node:
					tmp.append(ch)
					dfs(node[ch], tmp, res)
					tmp.pop()
		(res, tmp) = ([], [])
		dfs(self.root, tmp, res)
		return res

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		t = Trie()
		for f in folder:
			t.insert(f + '/')
		return [f[:-1] for f in t.search()]
		n = len(folder)
		folder = [f + '/' for f in folder]
		folder.sort()
		parent = 0
		for child in range(1, n):
			if folder[child].startswith(folder[parent]):
				folder[child] = None
			else:
				parent = child
		return [f[:-1] for f in folder if f is not None]


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort(key=lambda x: len(x))
		folderDict = {}
		ans = set(folder)
		for address in folder:
			aList = address[1:].split('/')
			pointer = folderDict
			for name in aList:
				if name in pointer:
					pointer = pointer[name]
					if '$' in pointer:
						if address in ans:
							ans.remove(address)
				else:
					pointer[name] = {}
					pointer = pointer[name]
			pointer['$'] = ''
		return ans


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:

		class Node:

			def __init__(self):
				self.is_path = False
				self.subs = {}

			def add_path(self, p, i=0):
				if i == len(p):
					return
				n = p[i]
				if n not in self.subs:
					self.subs[n] = Node()
				self.subs[n].is_path |= len(p) - i == 1
				self.subs[n].add_path(p, i + 1)
		t = Node()
		for f in folder:
			p = f.split('/')[1:]
			t.add_path(p)
		s = []
		p = []

		def dfs_visit(r, name=''):
			if r.is_path is True:
				s.append('/'.join(p) + '/' + name)
				return
			p.append(name)
			for (sub_name, sub) in r.subs.items():
				dfs_visit(sub, sub_name)
			p.pop()
		dfs_visit(t)
		return s


class TrieNode:

	def __init__(self):
		self.children = {}
		self.end = False

class Trie:

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

	def insert(self, path):
		node = self.root
		for ch in path:
			if ch not in node.children:
				node.children[ch] = TrieNode()
			node = node.children[ch]
		node.end = '/' + '/'.join(path)

	def find(self):

		def dfs(aggregate, node):
			if node.end:
				result.append(node.end)
				return
			for ch in node.children:
				dfs(aggregate + [ch], node.children[ch])
		result = []
		dfs([], self.root)
		return result

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		if not folder:
			return []
		trie = Trie()
		for path in folder:
			splitPaths = path.split('/')[1:]
			trie.insert(splitPaths)
		returnList = trie.find()
		return returnList


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isEnd = False

class Trie:

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

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

	def find(self):

		def dfs(path, node):
			if node.isEnd:
				ans.append('/' + '/'.join(path))
				return
			for c in node.children:
				dfs(path + [c], node.children[c])
		ans = []
		dfs([], self.root)
		return ans

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = Trie()
		for f in folder:
			f = f.split('/')[1:]
			trie.insert(f)
		return trie.find()


class Node:

	def __init__(self):
		self.next = {}
		self.folder = False

class Trie:

	def __init__(self):
		self.root = Node()

	def update(self, folder):
		start = 1
		node = self.root
		while node and start < len(folder):
			i = start
			while i < len(folder) and folder[i] != '/':
				i += 1
			curr_fold = folder[start:i]
			if curr_fold not in node.__next__:
				node.next[curr_fold] = Node()
			node = node.next[curr_fold]
			start = i + 1
		node.folder = True

	def find_all(self):
		output = []

		def helper(node, path):
			if node.folder:
				output.append(path)
			else:
				for next_node in node.__next__:
					helper(node.next[next_node], path + '/' + next_node)
		helper(self.root, '')
		return output

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder_trie = Trie()
		for fold in folder:
			folder_trie.update(fold)
		return folder_trie.find_all()


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		res = [folder.pop(0)]
		n = len(folder)
		for i in range(n):
			pattern = f'^{res[-1]}/'
			result = re.match(pattern, folder[i])
			if not result:
				res += [folder[i]]
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		n = len(folder)
		prev = folder[0]
		i = 1
		while i < n:
			curr = folder[i]
			if curr.startswith(prev + '/'):
				folder.remove(curr)
				curr = prev
				i -= 1
				n -= 1
			prev = curr
			i += 1
		return folder


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		l = len(folder)
		i = 0
		while i < l - 1:
			p = folder[i]
			j = i + 1
			l = len(folder)
			while j < l:
				if folder[j].startswith(p):
					if len(folder[j]) > len(p) and folder[j][len(p)] == '/':
						folder.remove(folder[j])
						l = len(folder)
					else:
						j += 1
				else:
					break
			i += 1
		return folder


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isEnd = False

class Solution:

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

	def _add(self, path):
		node = self.root
		for string in path.split('/'):
			if not string:
				continue
			if string not in node.children:
				node.children[string] = TrieNode()
			node = node.children[string]
		node.isEnd = True
		return

	def _isSubFolder(self, path):
		node = self.root
		for string in path.split('/'):
			if not string:
				continue
			if node.isEnd:
				return True
			node = node.children[string]
		return False

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		res = []
		for path in folder:
			self._add(path)
		for path in folder:
			if not self._isSubFolder(path):
				res.append(path)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		folder_set = set(folder)
		n = len(folder)
		prev = folder[0]
		i = 1
		while i < n:
			curr = folder[i]
			(len_prev, len_curr) = (len(prev), len(curr))
			if len_prev < len_curr:
				if curr[:len_prev] in folder_set:
					if curr[len_prev] == '/':
						folder.remove(curr)
						curr = prev
						i -= 1
						n -= 1
			prev = curr
			i += 1
		return folder


class Solution:

	def removeSubfolders(self, folders: List[str]) -> List[str]:
		seen = set()
		folders.sort(key=lambda x: len(x))
		for folder in folders.copy():
			for i in range(2, len(folder)):
				if folder[i] == '/' and folder[:i] in seen:
					folders.remove(folder)
					break
			else:
				seen.add(folder)
		return folders


class Solution:

	def removeSubfolders(self, folders: List[str]) -> List[str]:
		seen = set()
		folders.sort(key=lambda x: len(x))
		for folder in folders.copy():
			folder_split = folder.split('/')[1:]
			for i in range(len(folder_split)):
				if tuple(folder_split[:i + 1]) in seen:
					folders.remove(folder)
					break
			else:
				seen.add(tuple(folder_split))
		return folders


class Trie:

	def __init__(self):
		self.sub = collections.defaultdict(Trie)
		self.index = -1

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		self.root = Trie()
		for i in range(len(folder)):
			cur = self.root
			for c in folder[i]:
				cur = cur.sub[c]
			cur.index = i
		return self.bfs(self.root, folder)

	def bfs(self, trie: Trie, folder: List[str]) -> List[str]:
		(q, ans) = ([trie], [])
		for t in q:
			if t.index >= 0:
				ans.append(folder[t.index])
			for c in t.sub.keys():
				if '/' != c or t.index < 0:
					q.append(t.sub.get(c))
		return ans


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder_subs = []
		folder.sort(key=len)
		for f in folder:
			flag = False
			for j in folder_subs:
				if f.startswith(j + '/'):
					flag = True
					break
			if not flag:
				folder_subs.append(f)
		return folder_subs


class Trie:

	def __init__(self):
		self.sub = collections.defaultdict(Trie)
		self.index = -1

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		root = Trie()
		for i in range(len(folder)):
			curr = root
			for c in folder[i]:
				curr = curr.sub[c]
			curr.index = i
		(q, res) = ([root], [])
		for t in q:
			if t.index >= 0:
				res.append(folder[t.index])
			for c in t.sub.keys():
				if c != '/' or t.index < 0:
					q.append(t.sub.get(c))
		return res


class Trie:

	def __init__(self):
		self.children = collections.defaultdict(Trie)
		self.index = -1

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		self.root = Trie()
		for (i, f) in enumerate(folder):
			curr = self.root
			for ch in f:
				curr = curr.children[ch]
			curr.index = i
		return self.bfs(self.root, folder)

	def bfs(self, trie, folder):
		q = [trie]
		res = []
		for node in q:
			if node.index >= 0:
				res.append(folder[node.index])
				for c in node.children:
					if c != '/':
						q.append(node.children[c])
			else:
				for c in node.children:
					q.append(node.children[c])
		return res


class Solution:

	def removeSubfolders(self, folders: List[str]) -> List[str]:
		folders.sort()
		first = folders[0]
		res_set = set()
		res_set.add(first)
		for i in range(1, len(folders)):
			folder = folders[i]
			if folder.startswith(first) and folder.count('/') > first.count('/'):
				pass
			else:
				res_set.add(folder)
				res_set.add(first)
				first = folder
		res = list(res_set)
		res.sort()
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:

		class TrieNode:

			def __init__(self):
				self.children = defaultdict(TrieNode)
				self.index = -1
		res = []
		root = TrieNode()
		for i in range(len(folder)):
			trie = root
			for c in folder[i]:
				trie = trie.children[c]
			trie.index = i
		res = []
		q = [root]
		while q:
			node = q.pop(0)
			if node.index != -1:
				res.append(folder[node.index])
			for c in node.children.keys():
				if node.index < 0 or c != '/':
					q.append(node.children[c])
		return res


class Solution:

	class TrieNode:

		def __init__(self):
			self.lookup = {}
			self.word = False

	class Trie:

		def __init__(self):
			self.root = Solution.TrieNode()

		def addPath(self, word):
			currNode = self.root
			for char in word:
				if char not in currNode.lookup:
					currNode.lookup[char] = Solution.TrieNode()
				currNode = currNode.lookup[char]
			currNode.word = True

		def shortPath(self, word):
			currNode = self.root
			for (index, char) in enumerate(word):
				if currNode.word and char == '/':
					return word[:index]
				currNode = currNode.lookup[char]
			return word

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = Solution.Trie()
		result = set()
		for path in folder:
			trie.addPath(path)
		for path in folder:
			result.add(trie.shortPath(path))
		return list(result)


from collections import deque

class TrieNode:

	def __init__(self):
		self.children = {}
		self.is_word = False

class Trie:

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

	def insert(self, word):
		p = self.root
		for c in word:
			if c not in p.children:
				p.children[c] = TrieNode()
			p = p.children[c]
		p.is_word = True
		return p

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		if folder is None or not folder:
			return []
		trie = Trie()
		for f in folder:
			trie.insert(f)
		ret = []
		queue = deque([(trie.root, '')])
		while queue:
			(p, acc) = queue.popleft()
			if p.is_word:
				ret.append(acc)
			for letter in p.children:
				if p.is_word and letter == '/':
					continue
				queue.append((p.children[letter], acc + letter))
		return ret


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:

		def insert(f):
			t = r
			for c in f:
				if c not in t.ch:
					t.ch[c] = TrieNode()
				t = t.ch[c]
			t.ch['/'] = TrieNode()
			t = t.ch['/']
			t.d = True

		def search(f):
			t = r
			for c in f:
				t = t.ch[c]
				if t.d:
					return False
			return True
		r = TrieNode()
		for f in folder:
			insert(f)
		l = []
		for f in folder:
			if search(f):
				l.append(f)
		return l

class TrieNode:

	def __init__(self):
		self.ch = {}
		self.d = False


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		ans = []
		seen = set(folder)
		for i in folder:
			path = i
			while path:
				path = path[:path.rfind('/')]
				if path in seen:
					break
			else:
				ans.append(i)
		return ans


def is_parent(f1, f2):
	f1 = f1.split('/')
	f2 = f2.split('/')
	if len(f1) > len(f2):
		return False
	for (a, b) in zip(f1, f2):
		if a != b:
			return False
	return True

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder = sorted(folder)
		ans = []
		for f in folder:
			if not ans or not is_parent(ans[-1], f):
				ans.append(f)
		return ans


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		ans = [folder[0]]
		prev = folder[0] + '/'
		for f in folder[1:]:
			if not f.startswith(prev):
				ans.append(f)
				prev = f + '/'
		return ans


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort(key=lambda f: len(f))
		seen = set()
		for f in folder:
			for i in range(2, len(f)):
				if f[i] == '/' and f[:i] in seen:
					break
			else:
				seen.add(f)
		return list(seen)


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		if not folder:
			return None
		folder.sort(key=lambda x: len(x))
		seen = set()
		for fold in folder:
			for i in range(2, len(fold)):
				if fold[i] == '/' and fold[:i] in seen:
					break
			else:
				seen.add(fold)
		return list(seen)


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder = sorted(folder, key=lambda e: len(e))
		res = set()
		for f in folder:
			flag = True
			for i in range(2, len(f)):
				if f[i] == '/' and f[:i] in res:
					flag = False
					break
			if flag:
				res.add(f)
		return list(res)


class TrieNode:

	def __init__(self):
		self.d = {}
		self.w = False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder = sorted(folder)
		root = TrieNode()
		res = []
		for file in folder:
			p = root
			end = False
			for w in file.split('/'):
				if p.w:
					end = True
					break
				if w not in p.d:
					p.d[w] = TrieNode()
				p = p.d[w]
			if end:
				continue
			p.w = True
			res.append(file)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = {}
		for f in folder:
			path = f.split('/')[1:]
			cur = trie
			for (idx, p) in enumerate(path):
				if idx == len(path) - 1:
					cur[p] = '#'
				elif p in cur:
					if cur[p] != '#':
						cur = cur[p]
					else:
						break
				else:
					cur[p] = {}
					cur = cur[p]
		ans = []

		def dfs(cur_dir, path):
			if cur_dir == '#':
				ans.append('/' + '/'.join(path))
				return
			for k in cur_dir:
				dfs(cur_dir[k], path + [k])
			return
		dfs(trie, [])
		return ans


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		self.trie = {}
		for path in folder:
			node = self.trie
			for c in path.split('/'):
				if c not in node:
					node[c] = {}
				node = node[c]
			node['*'] = True
		res = []
		node = self.trie
		stack = [(node, [])]
		while len(stack):
			(node, prefix) = stack.pop()
			if '*' in node and node['*']:
				res.append('/'.join(prefix))
			else:
				for (k, v) in list(node.items()):
					stack.append((v, prefix + [k]))
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		res = []
		folder.sort(key=lambda x: len(x))
		seen = set()
		for f in folder:
			if not any((f[i] == '/' and f[:i] in seen for i in range(2, len(f)))):
				seen.add(f)
		return list(seen)


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		seen = set()
		for path in folder:
			if not any((path[i] == '/' and path[:i] in seen for i in range(2, len(path)))):
				seen.add(path)
		return seen


from collections import defaultdict

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		Trie = lambda : defaultdict(Trie)
		trie = Trie()
		for f in folder:
			t = trie
			for c in f[1:].split('/'):
				t = t[c]
			t[None] = None
		res = []

		def dfs(t, path=[]):
			if None in t:
				res.append('/' + '/'.join(path))
				return
			for (c, nt) in list(t.items()):
				path.append(c)
				dfs(nt, path)
				path.pop()
		dfs(trie)
		return res


class TreeNode:

	def __init__(self, val):
		self.val = val
		self.folders = {}
		self.exist = False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		self.tree = TreeNode('.')
		for this_folder in folder:
			path = this_folder.split('/')[1:]
			pointer = self.tree
			for name in path:
				if pointer.exist:
					break
				if name not in pointer.folders:
					pointer.folders[name] = TreeNode(name)
				pointer = pointer.folders[name]
			pointer.exist = True
		ret = []

		def buildPath(curr, path):
			if curr is None:
				return
			if curr.exist:
				ret.append(path)
				return
			for (sub_name, sub) in curr.folders.items():
				buildPath(sub, path + '/' + sub_name)
		buildPath(self.tree, '')
		return ret


class TreeNode:

	def __init__(self):
		self.val = '/'
		self.children = {}
		self.isleaf = False

	def insert(self, val):
		if not val:
			self.isleaf = True
			return
		if val[0] in self.children:
			self.children[val[0]].insert(val[1:])
			return
		newnode = TreeNode()
		newnode.val = val[0]
		self.children[val[0]] = newnode
		newnode.insert(val[1:])

	def isparent(self, val):
		if val and val[0] in self.children:
			return self.children[val[0]].isleaf or self.children[val[0]].isparent(val[1:])
		return False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder = sorted(folder)
		ans = []
		fs = TreeNode()
		for f in folder:
			has_parent = fs.isparent(f.split('/'))
			if not has_parent:
				ans.append(f)
				fs.insert(f.split('/'))
		return ans


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		res = []
		for f in sorted(folder):
			if not res or not f.startswith(res[-1] + '/'):
				res.append(f)
		return res


class TreeNode:

	def __init__(self):
		self.val = '/'
		self.children = []
		self.isleaf = False

	def insert(self, val):
		if not val:
			self.isleaf = True
			return
		for child in self.children:
			if child.val == val[0]:
				child.insert(val[1:])
				return
		newnode = TreeNode()
		newnode.val = val[0]
		self.children.append(newnode)
		newnode.insert(val[1:])

	def isparent(self, val):
		for child in self.children:
			if child.val == val[0]:
				if child.isleaf:
					return True
				return child.isparent(val[1:])
		return False

def is_parent(f1, f2):
	f1 = f1.split('/')
	f2 = f2.split('/')
	if len(f1) > len(f2):
		return False
	return all([a == b for (a, b) in zip(f1, f2)])

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder = sorted(folder)
		ans = []
		fs = TreeNode()
		for f in folder:
			has_parent = fs.isparent(f.split('/'))
			if not has_parent:
				ans.append(f)
				fs.insert(f.split('/'))
		return ans


class Node:

	def __init__(self):
		self.children = {}
		self.is_word = False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		if folder is None or not folder:
			return []
		root = self._create_tree(folder)
		ret = []
		self._helper(root, [], ret)
		return ret

	def _helper(self, p, acc, ret):
		if p.is_word:
			ret.append('/' + '/'.join(acc))
			return
		for c in p.children:
			acc.append(c)
			self._helper(p.children[c], acc, ret)
			acc.pop()

	def _create_tree(self, folder):
		root = Node()
		for f in folder:
			t = f.split('/')
			p = root
			for i in range(1, len(t)):
				if p.is_word:
					break
				name = t[i]
				if name not in p.children:
					p.children[name] = Node()
				p = p.children[name]
			p.is_word = True
			p.children = {}
		return root


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = {}
		tokens = {path: path.split('/') for path in folder}
		for path in folder:
			curr = trie
			for token in tokens[path]:
				if '#' in curr:
					break
				if token not in curr:
					curr[token] = {}
				curr = curr[token]
			curr['#'] = True
		paths = set(folder)
		for path in folder:
			curr = trie
			for token in tokens[path]:
				if '#' in curr:
					paths.remove(path)
					break
				curr = curr[token]
		return list(paths)


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = {}
		for path in folder:
			curr = trie
			for f in path.split('/'):
				if f in curr:
					curr = curr[f]
				else:
					curr[f] = {}
					curr = curr[f]
			curr[None] = None
		res = []
		for path in folder:
			curr = trie
			issub = False
			for f in path.split('/'):
				if None in curr:
					issub = True
				else:
					curr = curr[f]
			if not issub:
				res.append(path)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = dict()
		trie[''] = [0, dict()]
		for f in folder:
			curr = trie
			prev = None
			for c in f.split('/'):
				if c not in curr:
					curr[c] = [0, dict()]
				prev = curr
				curr = curr[c][1]
			prev[c][0] = 1
		clean = []
		stack = [([''], trie[''])]
		while stack:
			(p, (isPath, d)) = stack.pop()
			if isPath == 0:
				for c in d:
					stack.append((p + [c], d[c]))
			else:
				clean.append('/'.join(p))
		return clean


class Node:

	def __init__(self, v):
		self.v = v
		self.children = {}

	def __repr__(self):
		return f'Node({self.v} {self.children.keys()})'

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = Node('')
		for f in folder:
			self.add_to_trie(trie, f)
		return ['/' + '/'.join(i) for i in self.dfs(trie)]

	def dfs(self, cur):
		if not cur.children:
			return [[]]
		res = []
		for (child, child_node) in cur.children.items():
			for sub_res in self.dfs(child_node):
				res.append([child] + sub_res)
		return res

	def add_to_trie(self, trie, f):
		if not f:
			return
		sub_folders = f.split('/')[1:]
		if sub_folders[0] in trie.children:
			cur = trie
			for (i, sub_folder) in enumerate(sub_folders):
				if sub_folder not in cur.children and (not cur.children):
					return
				elif sub_folder not in cur.children:
					self.add_subs_to_trie(cur, i, sub_folders)
					return
				else:
					cur = cur.children[sub_folder]
			if cur.children:
				cur.children = {}
		else:
			self.add_subs_to_trie(trie, 0, sub_folders)

	def add_subs_to_trie(self, trie, ix, sub_folders):
		cur = trie
		for i in range(ix, len(sub_folders)):
			sub_folder = sub_folders[i]
			cur.children[sub_folder] = Node(sub_folder)
			cur = cur.children[sub_folder]


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		if len(folder) == 1:
			return folder
		folder.sort()
		i = 0
		while i < len(folder) - 1:
			if folder[i + 1].startswith(folder[i] + '/'):
				folder.pop(i + 1)
			else:
				i += 1
		return folder


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		tmp = '*'
		res = []
		for elem in sorted(folder):
			if not elem.startswith(tmp):
				tmp = elem + '/'
				res.append(elem)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		res = set()
		folder.sort(key=len)
		for fold in folder:
			flag = 0
			for i in range(2, len(fold)):
				if fold[i] == '/':
					if fold[:i] in res:
						flag = 1
						break
			if flag == 0:
				res.add(fold)
		return list(res)


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		dicts = {}
		res = []
		folder.sort(key=lambda x: len(x))
		for fo in folder:
			candidates = []
			for i in range(len(fo)):
				if fo[i] == '/':
					candidates.append(i)
			candidates = candidates[1:]
			candidates.append(len(fo))
			add = True
			for can in candidates:
				if fo[:can] in dicts:
					add = False
					break
			if add:
				res.append(fo)
				dicts[fo] = 1
		return res


class Trie:

	def __init__(self):
		self.chi = collections.defaultdict(Trie)
		self.ise = False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		root = Trie()
		sta = []
		for x in sorted(folder):
			node = root
			tmp = x[1:].split('/')
			for y in tmp:
				node = node.chi[y]
				if node.ise:
					break
			else:
				node.ise = True
				sta.append(x)
		return sta


class Trie:

	def __init__(self):
		self.child = {}
		self.isLast = False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		if not folder:
			return []
		root = Trie()
		for sf in folder:
			lists = sf[1:].split('/')
			if lists:
				self.add(root, lists)
		res = []
		self.dfs(root, [], res)
		return res

	def dfs(self, root, temp, res):
		cur = root
		if cur.isLast:
			res += ('/' + '/'.join(temp),)
			return
		for ch in cur.child:
			self.dfs(cur.child[ch], temp + [ch], res)

	def add(self, root, lists):
		cur = root
		for elem in lists:
			if elem not in cur.child:
				cur.child[elem] = Trie()
			cur = cur.child[elem]
		cur.isLast = True


class TrieNode:

	def __init__(self):
		self.children = {}
		self.is_end = False

class Trie:

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

	def insert(self, pathes):
		node = self.root
		for p in pathes:
			if p not in node.children:
				node.children[p] = TrieNode()
			node = node.children[p]
		node.is_end = True

	def find(self):
		ans = []

		def dfs(pathes, node):
			if node.is_end:
				ans.append('/' + '/'.join(pathes))
				return
			for p in node.children:
				dfs(pathes + [p], node.children[p])
		dfs([], self.root)
		return ans

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = Trie()
		for f in folder:
			trie.insert(f.split('/')[1:])
		return trie.find()


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		res = []
		pfix = set()
		removed = set()
		for f in folder:
			valid = f.split('/')
			for i in range(0, len(valid)):
				target = '/'.join(valid[0:i + 1])
				if target in pfix:
					removed.add(f)
			pfix.add(f)
		return set(folder) - set(removed)


class TrieNode:

	def __init__(self):
		self.children = dict()
		self.path = None

class Solution:

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

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		for directory in folder:
			curr = self.root
			for f in directory.split('/')[1:]:
				if f not in curr.children:
					curr.children[f] = TrieNode()
				curr = curr.children[f]
			curr.path = directory

		def trie_search(node, res):
			if node.path:
				res.append(node.path)
				return res
			for nbr in node.children:
				res = trie_search(node.children[nbr], res)
			return res
		return trie_search(self.root, [])


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		x = sorted(folder)
		res = [x[0]]
		for i in range(1, len(x)):
			if x[i].startswith(res[-1]) and x[i][len(res[-1])] == '/':
				continue
			res.append(x[i])
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		n = len(folder)
		folder = sorted(folder)
		first = folder[0]
		ans = set()
		ans.add(folder[0])
		for i in range(1, n):
			flag = True
			second = folder[i]
			first1 = first.split('/')
			second1 = second.split('/')
			for j in range(len(first1)):
				if first1[j] != second1[j]:
					ans.add(second)
					first = second
					flag = False
					break
		return list(ans)


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort(key=len)
		res = []
		seen = set()
		for path in folder:
			tmp = []
			for d in path.split('/')[1:]:
				tmp.append(d)
				if '/'.join(tmp) in seen:
					break
			else:
				seen.add('/'.join(tmp))
				res.append(path)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		s = sorted(folder)
		fs = []
		while s:
			fs.append(s[0])
			s.pop(0)
			while s and self.is_subfolder(fs[-1], s[0]):
				s.pop(0)
		return fs

	def is_subfolder(self, x, y):
		x = x.split('/')
		y = y.split('/')
		if len(x) >= len(y):
			return False
		for (i, c) in enumerate(x):
			if c != y[i]:
				return False
		return True


class Node:

	def __init__(self):
		self.children = {}
		self.isLeaf = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, path: List[str]) -> None:
		node = self.root
		for directory in path:
			if directory not in node.children:
				node.children[directory] = Node()
			node = node.children[directory]
		node.isLeaf = True

	def search(self, path: List[str]) -> bool:
		node = self.root
		for directory in path:
			if directory not in node.children:
				return False
			node = node.children[directory]
		return node.isLeaf

	def startWith(self, path: List[str]) -> bool:
		node = self.root
		for directory in path:
			if directory not in node.children:
				return False
			node = node.children[directory]
		return True

	def isSubfolder(self, path: List[str]) -> bool:
		node = self.root
		for directory in path:
			if node.isLeaf:
				return True
			node = node.children[directory]
		return False

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = Trie()
		for path in folder:
			directories = path.split('/')
			trie.insert(directories)
		res = []
		for path in folder:
			directories = path.split('/')
			if not trie.isSubfolder(directories):
				res.append(path)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort()
		result = []
		splitted = list(map(lambda path: path.split('/')[1:], folder))
		numPath = len(folder)
		i = 0
		while i < numPath:
			result.append(folder[i])
			current = splitted[i]
			while i < numPath:
				remove = True
				for k in range(min(len(splitted[i]), len(current))):
					if splitted[i][k] != current[k]:
						remove = False
						break
				if remove:
					i += 1
				else:
					break
		return result


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = {}
		for f in folder:
			fo = f.split('/')
			curr = trie
			for letter in fo:
				if letter not in curr:
					curr[letter] = {}
				curr = curr[letter]
			curr['#'] = f

		def dfs(curr):
			if '#' in curr:
				res.append(curr['#'])
				return
			for key in curr:
				dfs(curr[key])
		res = []
		dfs(trie)
		return res


class Node:

	def __init__(self, name):
		self.name = name
		self.subdir = {}
		self.terminal = False

	def link(self, name, node):
		self.subdir[name] = node

class Solution:

	def dfs(self, node, dirstr, found):
		rtn = []
		if node.terminal and (not found):
			rtn = [dirstr]
		for x in node.subdir.keys():
			rtn = rtn + self.dfs(node.subdir[x], dirstr + '/' + x, found | node.terminal)
		return rtn

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		root = Node('')
		for d in folder:
			seq = d.split('/')[1:]
			p = root
			for f in seq:
				if f not in p.subdir:
					q = Node(f)
					p.subdir[f] = q
				p = p.subdir[f]
			p.terminal = True
		return self.dfs(root, '', False)


class TrieNode:

	def __init__(self):
		self.children = collections.defaultdict(TrieNode)
		self.is_word = ''

class Trie:

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

	def insert(self, word):
		curr = self.root
		for ch in word:
			curr = curr.children[ch]
		curr.is_word = '/' + '/'.join(word)

class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = Trie()
		for path in folder:
			trie.insert(path.split('/')[1:])
		res = []

		def bfs(node):
			if node.is_word:
				res.append(node.is_word)
				return
			for child in list(node.children.values()):
				bfs(child)
		bfs(trie.root)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:

		def check(f):
			return all(map(lambda x: len(x) > 0, f.split('/')[1:]))

		def parent(f):
			parents = set()
			tmp = f.split('/')
			for i in range(1, len(tmp) - 1):
				parents.add('/'.join(tmp[:i + 1]))
			return parents
		folder.sort()
		seen = set()
		res = []
		for f in folder:
			if check(f):
				flag = False
				ps = parent(f)
				for p in ps:
					if p in seen:
						flag = True
						break
				if not flag:
					res.append(f)
				seen.add(f)
		return res


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		folder.sort(key=lambda x: len(x))
		res = []
		files = sorted(folder)
		stack = [files[0]]
		for i in range(1, len(files)):
			if not files[i].startswith(stack[-1] + '/'):
				stack.append(files[i])
		return stack


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		trie = {}
		for f in folder:
			p = trie
			for c in f:
				if c not in p:
					p[c] = {}
				p = p[c]
			if '/' not in p:
				p['/'] = {}
			p = p['/']
			p['$'] = f
		ans = []
		for f in folder:
			p = trie
			full = f + '/'
			for c in full:
				if '$' in p:
					break
				p = p[c]
			else:
				ans.append(f)
		return ans


class Solution:

	def removeSubfolders(self, folder: List[str]) -> List[str]:
		dic = set(folder)
		for x in folder:
			for i in range(len(x)):
				if i != 0 and x[i] == '/':
					if x[:i] in dic:
						dic.remove(x)
						break
		return list(dic)