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

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

class Trie {
    String name;
    boolean isFile;
    StringBuilder content = new StringBuilder();
    Map<String, Trie> children = new HashMap<>();

    Trie insert(String path, boolean isFile) {
        Trie node = this;
        String[] ps = path.split("/");
        for (int i = 1; i < ps.length; ++i) {
            String p = ps[i];
            if (!node.children.containsKey(p)) {
                node.children.put(p, new Trie());
            }
            node = node.children.get(p);
        }
        node.isFile = isFile;
        if (isFile) {
            node.name = ps[ps.length - 1];
        }
        return node;
    }

    Trie search(String path) {
        Trie node = this;
        String[] ps = path.split("/");
        for (int i = 1; i < ps.length; ++i) {
            String p = ps[i];
            if (!node.children.containsKey(p)) {
                return null;
            }
            node = node.children.get(p);
        }
        return node;
    }
}

class FileSystem {
    private Trie root = new Trie();

    public FileSystem() {
    }

    public List<String> ls(String path) {
        List<String> ans = new ArrayList<>();
        Trie node = root.search(path);
        if (node == null) {
            return ans;
        }
        if (node.isFile) {
            ans.add(node.name);
            return ans;
        }
        for (String v : node.children.keySet()) {
            ans.add(v);
        }
        Collections.sort(ans);
        return ans;
    }

    public void mkdir(String path) {
        root.insert(path, false);
    }

    public void addContentToFile(String filePath, String content) {
        Trie node = root.insert(filePath, true);
        node.content.append(content);
    }

    public String readContentFromFile(String filePath) {
        Trie node = root.search(filePath);
        return node.content.toString();
    }
}

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

type Trie struct {
	name     string
	isFile   bool
	content  strings.Builder
	children map[string]*Trie
}

func newTrie() *Trie {
	m := map[string]*Trie{}
	return &Trie{children: m}
}

func (this *Trie) insert(path string, isFile bool) *Trie {
	node := this
	ps := strings.Split(path, "/")
	for _, p := range ps[1:] {
		if _, ok := node.children[p]; !ok {
			node.children[p] = newTrie()
		}
		node, _ = node.children[p]
	}
	node.isFile = isFile
	if isFile {
		node.name = ps[len(ps)-1]
	}
	return node
}

func (this *Trie) search(path string) *Trie {
	if path == "/" {
		return this
	}
	node := this
	ps := strings.Split(path, "/")
	for _, p := range ps[1:] {
		if _, ok := node.children[p]; !ok {
			return nil
		}
		node, _ = node.children[p]
	}
	return node
}

type FileSystem struct {
	root *Trie
}

func Constructor() FileSystem {
	root := newTrie()
	return FileSystem{root}
}

func (this *FileSystem) Ls(path string) []string {
	var ans []string
	node := this.root.search(path)
	if node == nil {
		return ans
	}
	if node.isFile {
		ans = append(ans, node.name)
		return ans
	}
	for v := range node.children {
		ans = append(ans, v)
	}
	sort.Strings(ans)
	return ans
}

func (this *FileSystem) Mkdir(path string) {
	this.root.insert(path, false)
}

func (this *FileSystem) AddContentToFile(filePath string, content string) {
	node := this.root.insert(filePath, true)
	node.content.WriteString(content)
}

func (this *FileSystem) ReadContentFromFile(filePath string) string {
	node := this.root.search(filePath)
	return node.content.String()
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * obj := Constructor();
 * 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