Leetcode 1166 @ Design System Files

1166. Design File System

Medium

You are asked to design a file system which provides two functions:

• createPath(path, value): Creates a new path and associates a value to it if possible and returns True. Returns False if the path already exists or its parent path doesn't exist.
• get(path): Returns the value associated with a path or returns -1 if the path doesn't exist.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

Implement the two functions.

Please refer to the examples for clarifications.

Example 1:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

Example 2:

Input: 
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output: 
[null,true,true,2,false,-1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path doesn't exist.

Constraints:

• The number of calls to the two functions is less than or equal to 10^4 in total.
• 2 <= path.length <= 100
• 1 <= value <= 10^9

NOTE: create method has been changed on August 29, 2019 to createPath. Please reset to default code definition to get new method signature.

这道题思路很简单，只要把出现过的path和对应的文件当作key-value pair都存起来就好了，那么很容易想到hashmap来做。由于这里有层级递推地查找，也是个应用trie的case。所以hashmap or trie都可以做。

只是用trie的话，trieNode里面存的值，和"/"的处理需要注意。

问题还有follow up, 就是设计一个watch function, 是callback的功能，可以看一看java的callback。Callback就是说，如果在某个被watch的path下面新添了任何文件夹，或者有任何改动，就call callBack function，callback里面自定义干些事情，干什么都行。这样可以维护一个全局的callback数组，里面存被关照的path, 假如在create or create file时，查一下当前path是不是在callback array里面，如果在，就trigger callBack method after modification.

Hashmap的做法

class FileSystem {
    unordered_map<string, int> paths;
public:
    FileSystem() {
        
    }
    
    bool createPath(string path, int value) {
         if (paths.count(path) > 0)
            return false; 
         string cur;
         for (int i = 0; i<path.size(); i++)
         {
             if (i == 0 || path[i] != '/')
             {
                 cur += path[i];
             }
             else if (i != 0 && path[i] == '/')
             {
                 if (paths.count(cur) == 0)
                     return false;
                 else
                 {
                     cur += path[i];
                 }
             }
         }
         paths[path] = value;
         return true;
    }
    
    int get(string path) {
        if (!paths.empty() && paths.count(path) > 0)
        {
            return paths[path];
        }
        return -1;
    }
};

Trie的做法

struct TrieNode {
    unordered_map<string, TrieNode*> child;
    bool isFile;
    int content;

    TrieNode() {
        isFile = false;
        content = -1;
    }
};

class FileSystem {
private:
    TrieNode* root = nullptr;

    vector<string> split(string& path) {
        vector<string> result;
        stringstream ss(path);
        string s;
        while(getline(ss, s, '/'))
        {
            if (s != "")
            {
                result.push_back(s);
            }
        }
        return result;
    }

    bool insert(vector<string>& path, int value) {
        int n = path.size();
        TrieNode* cur = root;
        for (int i = 0; i < n; ++i) {
            if (cur -> child.find(path[i]) == cur -> child.end()) {
                if (i != n - 1) {
                    return false;
                }
                cur -> child[path[i]] = new TrieNode();
            }
            else {
                if (i == n - 1) {
                    return false; // the path already exist
                }
            }
            cur = cur -> child[path[i]];
        }
        cur -> isFile = true;
        cur -> content = value;
        return true;
    }

    int find(vector<string>& path) {
        int n = path.size();
        TrieNode* cur = root;
        for (int i = 0; i < n; ++i) {
            if (cur -> child.find(path[i]) == cur -> child.end()) {
                return -1;
            }
            cur = cur -> child[path[i]];
        }
        return cur -> content;
    }
public:
    FileSystem() {
        root = new TrieNode();
    }

    bool createPath(string path, int value) {
        vector<string> p = split(path);
        return insert(p, value);
    }

    int get(string path) {
        vector<string> p = split(path);
        return find(p);
    }
};