1233Delete the subfolder folder One question daily

2024-01-01

字数统计: 587字 | 阅读时长: 3min

topic：

Thought：

脑子里的构思yesDictionary tree，ButClanguage的Dictionary tree，Whether it isPython
still golangI won’t write。 So helpless can only look at the answer。
ylbThe big guy is right firstlistSort，Then traverse the list。

1.ifiBefore[len(ans[-1])]Just happensans[-1]The element is consistent，Explainiyes
ans[-1]Subfolder folder，Then skip。

2.ifyes["/a/b/c","/a/b/ca","/a/b/d"]This situation，Be alone1.的判断yes不够的，at this time
"/a/b/ca"Before缀and"/a/b/c"yes一样的，但yescaandc实际上yes两个不同的文件夹，So add a judgment front end
yes否yes/，"/a/b/ca"and"/a/b/c/a"中后者才会被判定yes前面一个元素的子集。

Dictionary tree没太看懂:
我们可以使用Dictionary tree存储数组 folder All folders in。
Dictionary tree的每个节点包含 children Field，Sub -nodes for storing the current nodes，as well as fid Field，
Used to store the folder corresponding to the current node in the array folder Bidding。

For array folder Each folder in it f，We will first f according to / Divide into several skewers，
Then start from the root node，依次将子串加入Dictionary tree中。Next，我们从根节点开始搜索Dictionary tree，
if当前节点的 fid Field不为 -1，则说明当前节点对应的文件夹yes答案数组中的一个文件夹，
We add it to the array and return。otherwise，We search for all sub -nodes of the current node，Finally return to the array of answers。

Code：

python3

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for i in folder[1:]:
            m, n = len(ans[-1]), len(i)
            # if它的长度大于等于答案数组中最后一个文件夹的长度，并且它Before缀包含答案数组的最后一个文件夹再加上一个 /
            if m >= n or not (ans[-1] == i[:m] and i[m] == '/'):
                ans.append(i)
        return ans
# Dictionary tree
class Trie:
    def __init__(self):
        self.children = {}
        self.fid = -1

    def insert(self, i, f):
        node = self
        ps = f.split('/')
        for p in ps[1:]:
            if p not in node.children:
                node.children[p] = Trie()
            node = node.children[p]
        node.fid = 1

    def search(self):
        def dfs(root):
            if root.fid != -1:
                ans.append(root.fid)
                return
            for child in root.children.values():
                dfs(child)
        ans = []
        dfs(self)
        return ans
    
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for i, f in enumerate(folder):
            trie.insert(i, f)
        return [folder[i] for i in trie.search()]

golang

func removeSubfolders(folder []string) (ans []string) {
	sort.Strings(folder)
	ans = []string{folder[0]}
	for _, i := range folder[1:] {
		m, n := len(ans[len(ans)-1]), len(i)
		if m >= n || !(ans[len(ans)-1] == i[:m] && i[m] == '/'){
			ans = append(ans, i)
		}
	}
	return 
}