Description#
Design a data structure that simulates an in-memory file system.
Implement the FileSystem class:
FileSystem()
Initializes the object of the system.List<String> ls(String path)
- If
path
is a file path, returns a list that only contains this file's name. - If
path
is a directory path, returns the list of file and directory names in this directory.
The answer should in lexicographic order.void mkdir(String path)
Makes a new directory according to the given path
. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.void addContentToFile(String filePath, String content)
- If
filePath
does not exist, creates that file containing given content
. - If
filePath
already exists, appends the given content
to original content.
String readContentFromFile(String filePath)
Returns the content in the file at filePath
.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0588.Design%20In-Memory%20File%20System/images/filesystem.png)
Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]
Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/"); // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/"); // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"
Constraints:
1 <= path.length, filePath.length <= 100
path
and filePath
are absolute paths which begin with '/'
and do not end with '/'
except that the path is just "/"
.- You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
- You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
1 <= content.length <= 50
- At most
300
calls will be made to ls
, mkdir
, addContentToFile
, and readContentFromFile
.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Trie:
def __init__(self):
self.name = None
self.isFile = False
self.content = []
self.children = {}
def insert(self, path, isFile):
node = self
ps = path.split('/')
for p in ps[1:]:
if p not in node.children:
node.children[p] = Trie()
node = node.children[p]
node.isFile = isFile
if isFile:
node.name = ps[-1]
return node
def search(self, path):
node = self
if path == '/':
return node
ps = path.split('/')
for p in ps[1:]:
if p not in node.children:
return None
node = node.children[p]
return node
class FileSystem:
def __init__(self):
self.root = Trie()
def ls(self, path: str) -> List[str]:
node = self.root.search(path)
if node is None:
return []
if node.isFile:
return [node.name]
return sorted(node.children.keys())
def mkdir(self, path: str) -> None:
self.root.insert(path, False)
def addContentToFile(self, filePath: str, content: str) -> None:
node = self.root.insert(filePath, True)
node.content.append(content)
def readContentFromFile(self, filePath: str) -> str:
node = self.root.search(filePath)
return ''.join(node.content)
# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.ls(path)
# obj.mkdir(path)
# obj.addContentToFile(filePath,content)
# param_4 = obj.readContentFromFile(filePath)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| class Trie {
String name;
boolean isFile;
StringBuilder content = new StringBuilder();
Map<String, Trie> children = new HashMap<>();
Trie insert(String path, boolean isFile) {
Trie node = this;
String[] ps = path.split("/");
for (int i = 1; i < ps.length; ++i) {
String p = ps[i];
if (!node.children.containsKey(p)) {
node.children.put(p, new Trie());
}
node = node.children.get(p);
}
node.isFile = isFile;
if (isFile) {
node.name = ps[ps.length - 1];
}
return node;
}
Trie search(String path) {
Trie node = this;
String[] ps = path.split("/");
for (int i = 1; i < ps.length; ++i) {
String p = ps[i];
if (!node.children.containsKey(p)) {
return null;
}
node = node.children.get(p);
}
return node;
}
}
class FileSystem {
private Trie root = new Trie();
public FileSystem() {
}
public List<String> ls(String path) {
List<String> ans = new ArrayList<>();
Trie node = root.search(path);
if (node == null) {
return ans;
}
if (node.isFile) {
ans.add(node.name);
return ans;
}
for (String v : node.children.keySet()) {
ans.add(v);
}
Collections.sort(ans);
return ans;
}
public void mkdir(String path) {
root.insert(path, false);
}
public void addContentToFile(String filePath, String content) {
Trie node = root.insert(filePath, true);
node.content.append(content);
}
public String readContentFromFile(String filePath) {
Trie node = root.search(filePath);
return node.content.toString();
}
}
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem obj = new FileSystem();
* List<String> param_1 = obj.ls(path);
* obj.mkdir(path);
* obj.addContentToFile(filePath,content);
* String param_4 = obj.readContentFromFile(filePath);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| type Trie struct {
name string
isFile bool
content strings.Builder
children map[string]*Trie
}
func newTrie() *Trie {
m := map[string]*Trie{}
return &Trie{children: m}
}
func (this *Trie) insert(path string, isFile bool) *Trie {
node := this
ps := strings.Split(path, "/")
for _, p := range ps[1:] {
if _, ok := node.children[p]; !ok {
node.children[p] = newTrie()
}
node, _ = node.children[p]
}
node.isFile = isFile
if isFile {
node.name = ps[len(ps)-1]
}
return node
}
func (this *Trie) search(path string) *Trie {
if path == "/" {
return this
}
node := this
ps := strings.Split(path, "/")
for _, p := range ps[1:] {
if _, ok := node.children[p]; !ok {
return nil
}
node, _ = node.children[p]
}
return node
}
type FileSystem struct {
root *Trie
}
func Constructor() FileSystem {
root := newTrie()
return FileSystem{root}
}
func (this *FileSystem) Ls(path string) []string {
var ans []string
node := this.root.search(path)
if node == nil {
return ans
}
if node.isFile {
ans = append(ans, node.name)
return ans
}
for v := range node.children {
ans = append(ans, v)
}
sort.Strings(ans)
return ans
}
func (this *FileSystem) Mkdir(path string) {
this.root.insert(path, false)
}
func (this *FileSystem) AddContentToFile(filePath string, content string) {
node := this.root.insert(filePath, true)
node.content.WriteString(content)
}
func (this *FileSystem) ReadContentFromFile(filePath string) string {
node := this.root.search(filePath)
return node.content.String()
}
/**
* Your FileSystem object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Ls(path);
* obj.Mkdir(path);
* obj.AddContentToFile(filePath,content);
* param_4 := obj.ReadContentFromFile(filePath);
*/
|