MediumNo. 1166LeetCode Premium
Design File System — LeetCode 1166 Python Solution
- Pattern
- Trie
- Topics
- Design, Trie, Hash Table, String
- Reading time
- 7 min
- Source
- leetcode.com
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
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
- Time
- O(|w|), where |w| is the length of the path w
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0208 | Implement Trie (Prefix Tree) | Medium |
| 0676 | Implement Magic Dictionary | Medium |
| 0677 | Map Sum Pairs | Medium |
| 0745 | Prefix and Suffix Search | Hard |
| 2227 | Encrypt and Decrypt Strings | Hard |
| 0139 | Word Break | Medium |
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.