Formatted question description: https://leetcode.ca/all/588.html

588. Design In-Memory File System

Level

Hard

Description

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

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 in this directory. Your output (file and directory names together) should in lexicographic order.

mkdir: Given a directory path that does not exist, you should make 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.

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 has void return type.

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

Example:

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:

Image text

Note:

You can assume all file or directory paths are absolute paths which begin with / and do not end with / except that the path is just "/".
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.
You can assume that all directory names and file names only contain lower-case letters, and same names won’t exist in the same directory.

Solution

Define a class Node. Each object of Node has a data field String path, a data field boolean isFile, and a data field List<Node> children. In FileSystem class, create a root of type Node. Besides, create a map that stores each file path with its corresponding content.

For the constructor, initialize the root and the map.

For method ls, find the node at the end of the path, and obtain the node’s children. If the node is a file, then use a list to store the file’s name and return the list. Otherwise, use a list to store the children’s paths and return the list.

For method mkdir, find all the nodes in the given path, and create the nodes if they do not exist.

For method addContentToFile, like mkdir, find all the nodes in the given path and create the nodes if they do not exist. For the last node which is the file, create the file using isFile = true. Then obtain the content of the file if it already exists, or an empty string otherwise, append the new content to the content, and update the file path with the updated content.

For method readContentFromFile, simply obtain the content from the map using the file path and return the content.

class FileSystem {
    Node root;
    Map<String, String> fileContentMap;

    public FileSystem() {
        root = new Node();
        fileContentMap = new HashMap<String, String>();
    }
    
    public List<String> ls(String path) {
        String[] array = path.substring(1).split("/");
        Node node = root;
        int length = path.length() == 1 ? 0 : array.length;
        for (int i = 0; i < length; i++) {
            String subPath = array[i];
            int index = binarySearch(node.children, subPath);
            if (index >= 0)
                node = node.children.get(index);
            else
                return new ArrayList<String>();
        }
        List<String> list = new ArrayList<String>();
        if (node.isFile) {
            String nodePath = node.path;
            list.add(node.path);
        } else {
            List<Node> children = node.children;
            int size = children.size();
            for (int i = 0; i < size; i++) {
                Node child = children.get(i);
                list.add(child.path);
            }
        }
        return list;
    }
    
    public void mkdir(String path) {
        if (path.equals("/"))
            return;
        String[] array = path.substring(1).split("/");
        Node node = root;
        int length = array.length;
        for (int i = 0; i < length; i++) {
            String subPath = array[i];
            int index = binarySearch(node.children, subPath);
            if (index >= 0)
                node = node.children.get(index);
            else {
                Node newNode = new Node(subPath, false);
                node.children.add(-index - 1, newNode);
                node = newNode;
            }
        }
    }
    
    public void addContentToFile(String filePath, String content) {
        String[] array = filePath.substring(1).split("/");
        Node node = root;
        int length = array.length - 1;
        for (int i = 0; i < length; i++) {
            String subPath = array[i];
            int index = binarySearch(node.children, subPath);
            if (index >= 0)
                node = node.children.get(index);
            else {
                Node newNode = new Node(subPath, false);
                node.children.add(-index - 1, newNode);
                node = newNode;
            }
        }
        Node fileNode = new Node(array[length], true);
        int index = binarySearch(node.children, array[length]);
        if (index < 0)
            node.children.add(-index - 1, fileNode);
        String prevContent = fileContentMap.getOrDefault(filePath, "");
        String newContent = prevContent + content;
        fileContentMap.put(filePath, newContent);
    }
    
    public String readContentFromFile(String filePath) {
        return fileContentMap.getOrDefault(filePath, "");
    }

    private int binarySearch(List<Node> list, String key) {
        int low = 0, high = list.size() - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            Node node = list.get(mid);
            if (node.path.equals(key))
                return mid;
            else if (node.path.compareTo(key) > 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -low - 1;
    }
}

class Node {
    String path;
    boolean isFile;
    List<Node> children;

    public Node() {
        this("", false);
    }

    public Node(String path, boolean isFile) {
        this.path = path;
        this.isFile = isFile;
        if (!isFile)
            children = new ArrayList<Node>();
    }
}

/**
 * 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);
 */

// OJ: https://leetcode.com/problems/design-in-memory-file-system/
struct File {
    bool isDirectory = true;
    map<string, File*> contents;
    string name, content;
    File(string name) : name(name) {}
};
class FileSystem {
    File root = File("");
    File *getFile(string path, bool createFile = false) {
        istringstream ss(path);
        string name;
        auto fp = &root;
        getline(ss, name, '/');
        while (getline(ss, name, '/')) {
            if (fp->contents.count(name) == 0) {
                fp->contents[name] = new File(name);
            }
            fp = fp->contents[name];
        }
        if (createFile) fp->isDirectory = false;
        return fp;
    }
public:
    FileSystem() {}
    vector<string> ls(string path) {
        auto fp = getFile(path);
        if (fp->isDirectory) {
            vector<string> ans;
            for (auto &[name, fp] : fp->contents) {
                ans.push_back(name);
            }
            return ans;
        }
        return { fp->name };
    }
    void mkdir(string path) {
        getFile(path);
    }
    void addContentToFile(string filePath, string content) {
        getFile(filePath, true)->content += content;
    }
    string readContentFromFile(string filePath) {
        return getFile(filePath)->content;
    }
};

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)

############

class FileNode(object):
  def __init__(self, name):
    self.isFolder = True
    self.childs = {}
    self.name = name
    self.data = ""

  def appendData(self, data):
    self.data += data

  def readAll(self):
    return self.data


class FileSystem(object):
  def __init__(self):
    self.root = FileNode("/")

  def ls(self, path):
    """
    :type path: str
    :rtype: List[str]
    """
    fd = self.lookup(path, False)
    if not fd:
      return []
    if not fd.isFolder:
      return [fd.name]
    files = []
    for file in fd.childs:
      files.append(file)
    files.sort()
    return files

  def lookup(self, path, isAutoCreate):
    path = path.split("/")
    p = self.root
    for name in path:
      if not name:
        continue
      if name not in p.childs:
        if isAutoCreate:
          p.childs[name] = FileNode(name)
        else:
          return None
      p = p.childs[name]
    return p

  def mkdir(self, path):
    """
    :type path: str
    :rtype: void
    """
    self.lookup(path, True)

  def addContentToFile(self, filePath, content):
    """
    :type filePath: str
    :type content: str
    :rtype: void
    """
    fd = self.lookup(filePath, True)
    fd.isFolder = False
    fd.appendData(content)

  def readContentFromFile(self, filePath):
    """
    :type filePath: str
    :rtype: str
    """
    fd = self.lookup(filePath, False)
    if fd:
      return fd.readAll()
    return ""

# 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)

Similar to the idea of Tire, each folder has its own files, together with a list of subfolders as children.

class FileSystem {

    class File{
        boolean isDir;
        ArrayList<File> children;
        String name;
        String content;
        public File(boolean isDir,String name){
            this.isDir = isDir;
            this.name = name;
            children = new ArrayList<>();
            content = new String("");
        }
    }
    
    File root;
    public FileSystem() {
        root = new File(true,"/");
    }
    
    public List<String> ls(String path) {
        File cur = getLast(path);
        if(cur.isDir){
            LinkedList<String> ret = new LinkedList<>();
            for(File file : cur.children){
                ret.add(file.name);
            }
            return ret;
        }else{
            LinkedList<String> ret = new LinkedList<>();
            ret.add(cur.name);
            return ret;
        }
    }
    
    public void mkdir(String path) {
        getAndCreate(path,true);
    }
    
    public void addContentToFile(String filePath, String content) {
        File f = getAndCreate(filePath,false);
        String contentnew = new String(f.content + content);
        f.content = contentnew;
    }
    
    public String readContentFromFile(String filePath) {
        File f =getLast(filePath);
        return f.content;
    }
    
    private File getLast(String path){
        File cur = root;
        path = path.substring(1);
        int idx = path.indexOf('/');
        while(idx >= 0){
            String curlvl = path.substring(0,idx);
            int found = searchFile(cur.children,curlvl);
            cur = cur.children.get(found);
            path = path.substring(idx+1);
            idx = path.indexOf('/');
        }
        int found = searchFile(cur.children,path);
        if(found < 0)
            return root;
        cur = cur.children.get(found);
        return cur;
    }
    
    private File getAndCreate(String path,boolean isDir){
        File cur = root;
        path = path.substring(1);
        int idx = path.indexOf('/');
        while(idx >= 0){
            String curlvl = path.substring(0,idx);
            if(cur.children.size() == 0){
                File dir = new File(true,curlvl);
                cur.children.add(dir);
                cur = dir;
                path = path.substring(idx+1);
                idx = path.indexOf('/');
                continue;
            }
            int found = searchFile(cur.children,curlvl);
            File tmp = cur.children.get(found);
            if(!tmp.name.equals(curlvl)){
                File dir = new File(true,curlvl);
                cur.children.add(found+1,dir);
                cur = dir;
                path = path.substring(idx+1);
                idx = path.indexOf('/');
                continue;
            }
            cur = tmp;
            path = path.substring(idx+1);
            idx = path.indexOf('/');
        }
        int found = searchFile(cur.children,path);
        if(found == -1 || !cur.children.get(found).name.equals(path)){
            File f = new File(isDir,path);
            if(cur.children.size() == 0){
                cur.children.add(f);
            }else{
                int foundLast = searchFile(cur.children,path);
                cur.children.add(foundLast+1,f);
            }
            cur = f;
        }else{
            cur = cur.children.get(found);
        }
        return cur;
    }
    
    private int searchFile(ArrayList<File> arr ,String name){
        if(arr.size() < 1)
            return -1;
        int lo = 0;
        int hi = arr.size()-1;
        int idx = -1;
        while(lo <= hi){
            int mid = (lo+hi)/2;
            if(arr.get(mid).name.equals(name))
                return mid;
            else if(arr.get(mid).name.compareTo(name)<0){
                idx = mid;
                lo = mid+1;
            }else{
                hi = mid-1;
            }
        }
        return idx;
    }
}

// OJ: https://leetcode.com/problems/design-in-memory-file-system/
struct File {
    bool isDirectory = true;
    map<string, File*> contents;
    string name, content;
    File(string name) : name(name) {}
};
class FileSystem {
    File root = File("");
    File *getFile(string path, bool createFile = false) {
        istringstream ss(path);
        string name;
        auto fp = &root;
        getline(ss, name, '/');
        while (getline(ss, name, '/')) {
            if (fp->contents.count(name) == 0) {
                fp->contents[name] = new File(name);
            }
            fp = fp->contents[name];
        }
        if (createFile) fp->isDirectory = false;
        return fp;
    }
public:
    FileSystem() {}
    vector<string> ls(string path) {
        auto fp = getFile(path);
        if (fp->isDirectory) {
            vector<string> ans;
            for (auto &[name, fp] : fp->contents) {
                ans.push_back(name);
            }
            return ans;
        }
        return { fp->name };
    }
    void mkdir(string path) {
        getFile(path);
    }
    void addContentToFile(string filePath, string content) {
        getFile(filePath, true)->content += content;
    }
    string readContentFromFile(string filePath) {
        return getFile(filePath)->content;
    }
};

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)

############

class FileNode(object):
  def __init__(self, name):
    self.isFolder = True
    self.childs = {}
    self.name = name
    self.data = ""

  def appendData(self, data):
    self.data += data

  def readAll(self):
    return self.data


class FileSystem(object):
  def __init__(self):
    self.root = FileNode("/")

  def ls(self, path):
    """
    :type path: str
    :rtype: List[str]
    """
    fd = self.lookup(path, False)
    if not fd:
      return []
    if not fd.isFolder:
      return [fd.name]
    files = []
    for file in fd.childs:
      files.append(file)
    files.sort()
    return files

  def lookup(self, path, isAutoCreate):
    path = path.split("/")
    p = self.root
    for name in path:
      if not name:
        continue
      if name not in p.childs:
        if isAutoCreate:
          p.childs[name] = FileNode(name)
        else:
          return None
      p = p.childs[name]
    return p

  def mkdir(self, path):
    """
    :type path: str
    :rtype: void
    """
    self.lookup(path, True)

  def addContentToFile(self, filePath, content):
    """
    :type filePath: str
    :type content: str
    :rtype: void
    """
    fd = self.lookup(filePath, True)
    fd.isFolder = False
    fd.appendData(content)

  def readContentFromFile(self, filePath):
    """
    :type filePath: str
    :rtype: str
    """
    fd = self.lookup(filePath, False)
    if fd:
      return fd.readAll()
    return ""

# 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)

588 - Design In-Memory File System

588. Design In-Memory File System

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

588. Design In-Memory File System

Level

Description

Solution

All Problems

All Solutions