Re: [閒聊] 每日leetcode
1233. Remove Sub-Folders from the Filesystem
## 思路
把folder都丟到Trie tree 並記錄是否為目錄尾 (is_end)
掃Trie tree時檢查is_end
## Code
```python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class TrieTree:
def __init__(self):
self.root = TrieNode()
def insert(self, path):
curr = self.root
for sub in path.split('/')[1:]:
if curr.is_end:
return
if sub not in curr.children:
curr.children[sub] = TrieNode()
curr = curr.children[sub]
curr.is_end = True
def get_all(self):
res = []
path = ['']
def recur(curr):
if curr.is_end:
res.append('/'.join(path))
return
for sub in curr.children:
path.append(sub)
recur(curr.children[sub])
path.pop()
recur(self.root)
return res
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
trie = TrieTree()
for path in folder:
trie.insert(path)
return trie.get_all()
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.147 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729854887.A.166.html
討論串 (同標題文章)
完整討論串 (本文為第 1044 之 1548 篇)：