Problem statement

https://leetcode.com/problems/design-file-system/

Solution

The idea is to use trie, where for each node (folder) we have set of subfolders. Function search will look for given path, starting with given node. It will return (False, None) if path was not found and (True, node) if it was found.

  1. createPath(self, path, value) will check of we have parental folder first, if not: return False. Then we check if we have this path already, if we have, return False. Finally, add new node to our trie and return True.
  2. get(self, path) will check if we have path in our trie, if not, return -1, if we have: return value.

Complexity

Time complexity of createPath, get is linear in lenght of input strings. Space complexity is potentially sum all all length of queries.

Code

class TrieNode:
    def __init__(self, ch = {}, val = 0):
        self.children = ch
        self.value = val

class Trie:
    def __init__(self):
        self.root = TrieNode({}, 0)

    def search(self, node, path):
        for folder in path:
            if folder in node.children:
                node = node.children[folder]
            else:
                return (False, None)
        return (True, node)

class FileSystem:
    def __init__(self):
        self.trie = Trie()

    def createPath(self, path, value):
        path = path.split("/")[1:]
        found, node = self.trie.search(self.trie.root, path[:-1])
        if node == None: return False
        if path[-1] in node.children: return False
        node.children.setdefault(path[-1], TrieNode({}, value))
        return True

    def get(self, path):
        path = path.split("/")[1:]
        found, node = self.trie.search(self.trie.root, path)
        if node == None: return -1
        return node.value

Remark

I have interesting effect here: if we initialize self.root = Trie(), then for some reason it will save copy of previous call for FileSystem, need to investigate