Question

588. Design In-Memory File System

中文文档

Description

Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

• FileSystem() Initializes the object of the system.
• List<String> ls(String path)
  • If path is a file path, returns a list that only contains this file's name.
  • If path is a directory path, returns the list of file and directory names in this directory.
  The answer should in lexicographic order.
• void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.
• void addContentToFile(String filePath, String content)
  • If filePath does not exist, creates that file containing given content.
  • If filePath already exists, appends the given content to original content.
• String readContentFromFile(String filePath) Returns the content in the file at filePath.

 

Example 1:

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
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/"); // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/"); // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

 

Constraints:

• 1 <= path.length, filePath.length <= 100
• path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/".
• You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
• 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.
• 1 <= content.length <= 50
• At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.

Solutions

Solution 1

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

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