05 August 2008
文件系统构成了一个树状结构，所以题目的一个解法就是建立一个树状结构来模拟文件系统。但是由于本题目是简化版的文件系统，所以我们也可以用更简单的字典树来实现。我们定义一个TrieNode的结构来统一表示文件和文件夹。如果isFile为true，则content表示文件的具体内容，此时children无效；否则children表示文件夹下的子文件（夹）列表，而content无效。下面给出各个函数的实现说明：
vector
void mkdir(string path)：按照path给出的路径，在字典树中找相应的文件夹，如果发现文件夹不存在，则新建文件夹。这样处理直到路径末尾。
void addContentToFile(string filePath, string content)：按照filePath给出的路径，在字典树中找相应的文件（如果文件或者文件夹不存在，则新建），最后将内容追加到找到（新建）的文件夹中即可。
string readContentFromFile(string filePath)：按照path给出的路径去找相应的文件，最后返回对应文件的内容即可。
Trie
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
class FileSystem {
class TrieNode {
Map<String, TrieNode> children = new HashMap<>();
String content;
boolean isFile = false;
public TrieNode(String content) {
this.content = content;
}
}
TrieNode root;
public FileSystem() {
root = new TrieNode("");
}
public List<String> ls(String path) {
TrieNode node = root;
String[] paths = path.split("/");
String name = "";
List<String> result = new ArrayList<>();
for (int i = 1; i < paths.length; i++) {
if (!node.children.containsKey(paths[i]))
return result;
node = node.children.get(paths[i]);
name = paths[i];
}
if (node.isFile) {
result.add(name);
} else {
result = new ArrayList<>(node.children.keySet());
}
result.sort(String::compareTo);
return result;
}
public void mkdir(String path) {
TrieNode node = root;
String[] paths = path.split("/");
for (int i = 1; i < paths.length; i++) {
if (!node.children.containsKey(paths[i])) {
node.children.put(paths[i], new TrieNode(""));
}
node = node.children.get(paths[i]);
}
}
public void addContentToFile(String filePath, String content) {
TrieNode node = root;
String[] paths = filePath.split("/");
for (int i = 1; i < paths.length; i++) {
if (!node.children.containsKey(paths[i])) {
node.children.put(paths[i], new TrieNode(""));
}
node = node.children.get(paths[i]);
}
node.isFile = true;
node.content += content;
}
public String readContentFromFile(String filePath) {
TrieNode node = root;
String[] paths = filePath.split("/");
for (int i = 1; i < paths.length; i++) {
if (!node.children.containsKey(paths[i])) {
return "";
}
node = node.children.get(paths[i]);
}
return node.content;
}
}
/**
* 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);
*/
HashMap
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
class FileSystem {
class Dir {
HashMap<String, Dir> dirs = new HashMap<>();
HashMap<String, String> files = new HashMap<>();
}
Dir root;
public FileSystem() {
root = new Dir();
}
public List<String> ls(String path) {
Dir t = root;
List<String> files = new ArrayList<>();
if (!path.equals("/")) {
String[] d = path.split("/");
for (int i = 1; i < d.length - 1; i++) {
t = t.dirs.get(d[i]);
}
if (t.files.containsKey(d[d.length - 1])) {
files.add(d[d.length - 1]);
return files;
} else {
t = t.dirs.get(d[d.length - 1]);
}
}
files.addAll(new ArrayList<>(t.dirs.keySet()));
files.addAll(new ArrayList<>(t.files.keySet()));
Collections.sort(files);
return files;
}
public void mkdir(String path) {
Dir t = root;
String[] d = path.split("/");
for (int i = 1; i < d.length; i++) {
if (!t.dirs.containsKey(d[i]))
t.dirs.put(d[i], new Dir());
t = t.dirs.get(d[i]);
}
}
public void addContentToFile(String filePath, String content) {
Dir t = root;
String[] d = filePath.split("/");
for (int i = 1; i < d.length - 1; i++) {
t = t.dirs.get(d[i]);
}
t.files.put(d[d.length - 1], t.files.getOrDefault(d[d.length - 1], "") + content);
}
public String readContentFromFile(String filePath) {
Dir t = root;
String[] d = filePath.split("/");
for (int i = 1; i < d.length - 1; i++) {
t = t.dirs.get(d[i]);
}
return t.files.get(d[d.length - 1]);
}
}
/**
* 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);
*/