本文共 2783 字，大约阅读时间需要 9 分钟。

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.

------------------------------------------------------------------------------

My code, simulate a trie tree:

class Node:    def __init__(self, val, terminal, lst):        self.val = val        self.terminal = terminal        self.names = lst        self.sons = {}class Solution:    def removeSubfolders(self, folder):        res = []        root = Node("", False, [])        for path in folder:            names = path.split('/')            cur = root            for name in names:                if (name):                    # bug1                    # lst = cur.names                    # lst.extend(name)                    # bug2                    if (name not in cur.sons): #bug3                        cur.sons[name] = Node(name, False, cur.names+[name])                    cur = cur.sons[name]            cur.terminal = True        layers = [{root}, set()]        c, n = 0, 1        while (layers[c]):            for node in layers[c]:                if (node.terminal == True):                    res.append('/' + '/'.join(node.names))                else:                    for k,v in node.sons.items():                        layers[n].add(v)            layers[c].clear()            c, n = n, c        return ress = Solution()print(s.removeSubfolders(["/a/b/c","/a/b/ca","/a/b/d"]))

From leetcode discussion:

class Solution:    def removeSubfolders(self, folder):        res = set()        folder.sort(key=lambda x:len(x))        for path in folder:            #bug1 path[i] == '/'            if (not any(path[i] == '/' and path[:i] in res for i in range(2,len(path)))):                res.add(path)        return list(res)s = Solution()print(s.removeSubfolders(["/a/b/c","/a/b/ca","/a/b/d"]))

转载地址：http://ztfoi.baihongyu.com/