Design File System — LeetCode 1166 Python Solution

MediumLeetCode PremiumDesignTrieHash TableString
Problem
#1166
Pattern
Trie
Reading time
7 min

The problem

You are asked to design a file system that allows you to create new paths and associate them with different values. The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters.

Example

Input
["FileSystem","createPath","get"]
Output
[null,true,1]
Explanation
FileSystem fileSystem = new FileSystem();

Python solution

Python
class Trie:
    def __init__(self, v: int = -1):
        self.children = {}
        self.v = v

    def insert(self, w: str, v: int) -> bool:
        node = self
        ps = w.split("/")
        for p in ps[1:-1]:
            if p not in node.children:
                return False
            node = node.children[p]
        if ps[-1] in node.children:
            return False
        node.children[ps[-1]] = Trie(v)
        return True

    def search(self, w: str) -> int:
        node = self
        for p in w.split("/")[1:]:
            if p not in node.children:
                return -1
            node = node.children[p]
        return node.v


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

    def createPath(self, path: str, value: int) -> bool:
        return self.trie.insert(path, value)

    def get(self, path: str) -> int:
        return self.trie.search(path)


# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.createPath(path,value)
# param_2 = obj.get(path)

Complexity

MeasureComplexity
TimeO(|w|), where |w| is the length of the path w
SpaceO(n) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1166. Design File System is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 1166. Design File System?
LeetCode 1166. Design File System is rated Medium on LeetCode.
What is the time complexity of LeetCode 1166. Design File System?
The Python solution on this page runs in O(|w|), where |w| is the length of the path w.
What is the space complexity of LeetCode 1166. Design File System?
The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1166. Design File System cover?
LeetCode 1166. Design File System is tagged Design, Trie, Hash Table and String on LeetCode.
Is LeetCode 1166. Design File System a premium problem?
Yes. LeetCode 1166. Design File System is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity — invisible to screen sharing.

Get Stealth Interview