← Static tasks

588. Design In-Memory File System

leetcode hard

#csharp#design#dynamic-programming#graph#hard#hash-table#leetcode#sort#string#tree

Task

Спроектируйте структуру данных, которая симулирует файловую систему в памяти.

Реализуйте класс FileSystem:

FileSystem() Инициализирует объект системы.

List<String> ls(String path)

Если path является путем к файлу, возвращает список, содержащий только имя этого файла.

Если path является путем к директории, возвращает список имен файлов и директорий в этой директории.

Ответ должен быть в лексикографическом порядке.

void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их.

void addContentToFile(String filePath, String content)

Если filePath не существует, создает файл, содержащий заданный контент.

Если filePath уже существует, добавляет заданный контент к исходному содержимому.

String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath.

Пример:

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"

C# solution

matched/original
public class FileSystem {
    class File {
        public bool isFile = false;
        public Dictionary<string, File> files = new Dictionary<string, File>();
        public string content = "";
    }
    File root = new File();
    private File Navigate(string path) {
        File t = root;
        if (path != "/") {
            var dirs = path.Split(new char[] { '/' });
            foreach (var dir in dirs) {
                if (!string.IsNullOrEmpty(dir)) {
                    if (!t.files.ContainsKey(dir)) {
                        t.files[dir] = new File();
                    }
                    t = t.files[dir];
                }
            }
        }
        return t;
    }
    public IList<string> Ls(string path) {
        var t = Navigate(path);
        if (t.isFile) return new List<string> { path.Substring(path.LastIndexOf("/") + 1) };
        var res = new List<string>(t.files.Keys);
        res.Sort();
        return res;
    }
    public void Mkdir(string path) {
        Navigate(path);
    }
    public void AddContentToFile(string filePath, string content) {
        var t = Navigate(filePath);
        t.isFile = true;
        t.content += content;
    }
    public string ReadContentFromFile(string filePath) {
        return Navigate(filePath).content;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class FileSystem {
    class File {
        public bool isFile = false;
        public unordered_map<string, File> files = new unordered_map<string, File>();
        public string content = "";
    }
    File root = new File();
    private File Navigate(string path) {
        File t = root;
        if (path != "/") {
            var dirs = path.Split(new char[] { '/' });
            foreach (var dir in dirs) {
                if (!string.IsNullOrEmpty(dir)) {
                    if (!t.files.count(dir)) {
                        t.files[dir] = new File();
                    }
                    t = t.files[dir];
                }
            }
        }
        return t;
    }
    public vector<string> Ls(string path) {
        var t = Navigate(path);
        if (t.isFile) return new List<string> { path.Substring(path.LastIndexOf("/") + 1) };
        var res = new List<string>(t.files.Keys);
        res.Sort();
        return res;
    }
    public void Mkdir(string path) {
        Navigate(path);
    }
    public void AddContentToFile(string filePath, string content) {
        var t = Navigate(filePath);
        t.isFile = true;
        t.content += content;
    }
    public string ReadContentFromFile(string filePath) {
        return Navigate(filePath).content;
    }
}

Java solution

matched/original
public class FileSystem {
    class File {
        boolean isFile = false;
        HashMap<String, File> files = new HashMap<>();
        String content = "";
    }
    
    File root = new File();

    public List<String> ls(String path) {
        File t = navigate(path);
        if (t.isFile) return Arrays.asList(path.substring(path.lastIndexOf("/") + 1));
        List<String> res = new ArrayList<>(t.files.keySet());
        Collections.sort(res);
        return res;
    }

    public void mkdir(String path) {
        navigate(path);
    }

    public void addContentToFile(String filePath, String content) {
        File t = navigate(filePath);
        t.isFile = true;
        t.content += content;
    }

    public String readContentFromFile(String filePath) {
        return navigate(filePath).content;
    }

    private File navigate(String path) {
        File t = root;
        if (!path.equals("/")) {
            for (String dir : path.split("/")) {
                if (!dir.isEmpty()) {
                    t.files.putIfAbsent(dir, new File());
                    t = t.files.get(dir);
                }
            }
        }
        return t;
    }
}

JavaScript solution

matched/original
class File {
    constructor() {
        this.isFile = false;
        this.files = new Map();
        this.content = "";
    }
}

class FileSystem {
    constructor() {
        this.root = new File();
    }

    navigate(path) {
        let t = this.root;
        if (path !== "/") {
            const dirs = path.split("/");
            for (const dir of dirs) {
                if (dir) {
                    if (!t.files.has(dir)) {
                        t.files.set(dir, new File());
                    }
                    t = t.files.get(dir);
                }
            }
        }
        return t;
    }

    ls(path) {
        const t = this.navigate(path);
        if (t.isFile) return [path.substring(path.lastIndexOf("/") + 1)];
        const res = Array.from(t.files.keys());
        res.sort();
        return res;
    }

    mkdir(path) {
        this.navigate(path);
    }

    addContentToFile(filePath, content) {
        const t = this.navigate(filePath);
        t.isFile = true;
        t.content += content;
    }

    readContentFromFile(filePath) {
        return this.navigate(filePath).content;
    }
}

Python solution

matched/original
class FileSystem:
    class File:
        def __init__(self):
            self.isfile = False
            self.files = {}
            self.content = ""

    def __init__(self):
        self.root = self.File()

    def ls(self, path: str) -> list:
        t = self._navigate(path)
        if t.isfile:
            return [path.split("/")[-1]]
        return sorted(t.files.keys())

    def mkdir(self, path: str) -> None:
        self._navigate(path)

    def addContentToFile(self, filePath: str, content: str) -> None:
        t = self._navigate(filePath)
        t.isfile = True
        t.content += content

    def readContentFromFile(self, filePath: str) -> str:
        return self._navigate(filePath).content

    def _navigate(self, path: str) -> 'File':
        t = self.root
        if path != "/":
            for dir in path.split("/"):
                if dir:
                    if dir not in t.files:
                        t.files[dir] = self.File()
                    t = t.files[dir]
        return t

Go solution

matched/original
package main

import (
  "sort"
  "strings"
)

type File struct {
  isFile bool
  files  map[string]*File
  content string
}

type FileSystem struct {
  root *File
}

func Constructor() FileSystem {
  return FileSystem{root: &File{files: make(map[string]*File)}}
}

func (this *FileSystem) navigate(path string) *File {
  t := this.root
  if path != "/" {
    dirs := strings.Split(path, "/")
    for _, dir := range dirs {
      if dir != "" {
        if _, ok := t.files[dir]; !ok {
          t.files[dir] = &File{files: make(map[string]*File)}
        }
        t = t.files[dir]
      }
    }
  }
  return t
}

func (this *FileSystem) Ls(path string) []string {
  t := this.navigate(path)
  if t.isFile {
    return []string{path[strings.LastIndex(path, "/")+1:]}
  }
  var res []string
  for name := range t.files {
    res = append(res, name)
  }
  sort.Strings(res)
  return res
}

func (this *FileSystem) Mkdir(path string) {
  this.navigate(path)
}

func (this *FileSystem) AddContentToFile(filePath string, content string) {
  t := this.navigate(filePath)
  t.isFile = true
  t.content += content
}

func (this *FileSystem) ReadContentFromFile(filePath string) string {
  return this.navigate(filePath).content
}

Explanation

Algorithm

Инициализация файловой системы:

Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content.

Обработка команд:

Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом.

Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их.

Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его.

Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути.

Обработка путей и работа с файлами/директориями:

Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов.

Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий.

😎