Skip to content

588. Design In-Memory File System 👍

  • Time:
  • Space:
 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
struct TrieNode {
  map<string, TrieNode*> children;  // map: lexicographical
  bool isFile = false;
  string content;
};

class FileSystem {
 public:
  vector<string> ls(string path) {
    auto [node, lastDir] = createDirAndGetPair(path);
    if (node->isFile)
      return {lastDir};

    vector<string> ans;

    for (const auto& [file, _] : node->children)
      ans.push_back(file);

    return ans;
  }

  void mkdir(string path) {
    createDirAndGetPair(path);
  }

  void addContentToFile(string filePath, string content) {
    TrieNode* node = createDirAndGetPair(filePath).first;
    node->isFile = true;
    node->content += content;
  }

  string readContentFromFile(string filePath) {
    TrieNode* node = createDirAndGetPair(filePath).first;
    return node->content;
  }

 private:
  TrieNode root;

  // createDirAndGetPair("/a//b") -> {TrieNode b, string "b"}
  pair<TrieNode*, string> createDirAndGetPair(const string& path) {
    const vector<string> dirs = getDirs(path);
    TrieNode* node = &root;

    for (const string& dir : dirs) {
      if (!node->children.count(dir))
        node->children[dir] = new TrieNode;
      node = node->children[dir];
    }

    return {node, dirs.empty() ? "" : dirs.back()};
  }

  // getDirs("/a//b") -> ["a", "b"]
  vector<string> getDirs(const string& path) {
    vector<string> dirs;
    istringstream iss(path);

    for (string dir; getline(iss, dir, '/');)
      if (!dir.empty())  // "/a//b" == "/a/b"
        dirs.push_back(dir);

    return dirs;
  }
};