Python, Straightforward with Explanation


  • 2

    We'll keep two structures, self.fs being a Trie, and self.fileinfo being a dictionary mapping filepaths to the string content in their files. For convenience, we can use a nested defaultdict structure instead of a proper Trie object. This means we should exercise caution as our call to TrieNode.__getitem__(child) has potential side effects if child is not in the node, but otherwise our code is very similar.

    Trie = lambda: collections.defaultdict(Trie)
    
    class FileSystem(object):
        def __init__(self):
            self.fs = Trie()
            self.fileinfo = collections.defaultdict(str)
            
        def ls(self, path):
            if path in self.fileinfo:
                return path.split('/')[-1:]
    
            cur = self.fs
            for token in path.split('/'):
                if token in cur:
                    cur = cur[token]
                elif token:
                    return []
    
            return sorted(cur.keys())
    
        def mkdir(self, path):
            cur = self.fs
            for token in path.split('/'):
                if token: cur = cur[token]
    
        def addContentToFile(self, filePath, content):
            self.mkdir(filePath)
            self.fileinfo[filePath] += content
    
        def readContentFromFile(self, filePath):
            return self.fileinfo[filePath]
    

    Here is the same solution using a TrieNode object.

    class Node(object):
        def __init__(self):
            self.children = {}
            
        def setdefault(self, token):
            return self.children.setdefault(token, Node())
            
        def get(self, token):
            return self.children.get(token, None)
                              
    class FileSystem(object):
        def __init__(self):
            self.root = Node()
            self.fileinfo = collections.defaultdict(str)
            
        def ls(self, path):
            if path in self.fileinfo:
                return path.split('/')[-1:]
    
            cur = self.root
            for token in path.split('/'):
                if cur and token:
                    cur = cur.get(token)
    
            return sorted(cur.children.keys()) if cur else []
    
        def mkdir(self, path):
            cur = self.root
            for token in path.split('/'):
                if token: cur = cur.setdefault(token)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.