Design In Memory File System - Leetcode Solution

The problem statement for Design In Memory File System on LeetCode is as follows:

Design an in-memory file system to simulate the following functions:

1. ls: Given a path in string format. If it is a file path, return a list that only contains this file's name. If it is a directory path, return the list of file and directory names under this directory in lexicographic order. The directory path is given in the Unix file format.

2. mkdir: Given a directory path that does not exist, you should create a new directory according to the path. If the middle directories in the path don't exist either, you should create them as well. This function has void return type.

3. addContentToFile: Given a file path and file content in string format. If the file doesn't exist, you need to create that file containing given content. If the file already exists, you need to append given content to original content. This function also has void return type.

4. readContentFromFile: Given a file path, return its content in string format.

Before we dive into the solution, we should first discuss the data structure that we will be using to store our file system.

We will be using a Trie data structure to represent our file system. Each Trie node will represent a directory or a file. If a node represents a directory, it will have a map of child nodes, where the keys are the child node names and the values are the child nodes themselves. If a node represents a file, it will have a content string that holds the file's content. We will also have a boolean flag in each node to indicate if the node represents a file or a directory.

With the data structure in mind, we can start implementing the four functions in our class.

class FileSystem {
    public:
        struct TrieNode {
            map<string, TrieNode*> children;
            bool is_file;
            string content;
            TrieNode(bool flag=false) {
                is_file = flag;
            }
        };
        FileSystem() {
            root = new TrieNode();
        }
        
        vector<string> ls(string path) {
            TrieNode* curr = traverse(path);
            if (curr->is_file) {
                return {split(path).back()};
            }
            vector<string> res;
            for (auto& p : curr->children) {
                res.push_back(p.first);
            }
            sort(res.begin(), res.end());
            return res;
        }
        
        void mkdir(string path) {
            traverse(path);
        }
        
        void addContentToFile(string filePath, string content) {
            TrieNode* curr = traverse(filePath);
            curr->is_file = true;
            curr->content += content;
        }
        
        string readContentFromFile(string filePath) {
            return traverse(filePath)->content;
        }
        
    private:
        TrieNode* root;
        
        vector<string> split(string path) {
            vector<string> res;
            string temp = "";
            for (int i = 1; i < path.size(); i++) {
                if (path[i] == '/') {
                    res.push_back(temp);
                    temp = "";
                }
                else {
                    temp += path[i];
                }
            }
            res.push_back(temp);
            return res;
        }
        
        TrieNode* traverse(string path) {
            TrieNode* curr = root;
            vector<string> paths = split(path);
            for (auto& p : paths) {
                if (curr->children.find(p) == curr->children.end()) {
                    curr->children[p] = new TrieNode();
                }
                curr = curr->children[p];
            }
            return curr;
        }
};

Let's go through the four functions one by one.

The ls function takes in a path and returns a vector of file and directory names under this directory if the path is a directory path, and a vector with only the name of the file if the path is a file. We first traverse the Trie to get the node that represents the file or directory at this path. If the node is a file, we return a vector with only this file name. If the node is a directory, we iterate through its child nodes and add their names to a vector. We then sort this vector and return it.

The mkdir function takes in a path and creates a directory according to this path. We first traverse the Trie to get the node that represents the deepest directory that exists in this path. Then we iterate through the rest of the path and create new nodes for each directory that doesn't exist yet.

The addContentToFile function takes in a file path and content, and either creates a new file with this content or appends the content to an existing file. We first traverse the Trie to get the node that represents this file. If this node doesn't exist yet, we create it and set its content to the given content. If it does exist, we append the given content to its original content.

The readContentFromFile function takes in a file path and returns the content of this file. We simply traverse the Trie to get the node that represents this file and return its content.

The time complexity of all four functions depends on the length of the input path. The worst case time complexity is O(n) where n is the length of the input path. The space complexity of the class is also O(n) where n is the total number of nodes in the Trie.

1