[LeetCode] Design In-Memory File System 設計記憶體檔案系統

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:

 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.

這道題讓我們設計一個記憶體檔案系統，實作顯示目前檔案，建立檔案，添加内容到檔案，讀取檔案内容等功能，感覺像是模拟一個terminal的一些指令。這道題比較tricky的地方是ls這個指令，題目中的例子其實不能很好的展示出ls的要求，其對檔案和檔案夾的處理方式是不同的。由于這裡面的檔案沒有字尾，是以最後一個字元串有可能是檔案，也有可能是檔案夾。比如a/b/c，那麼最後的c有可能是檔案夾，也有可能好是檔案，如果c是檔案夾的話，ls指令要輸出檔案夾c中的所有檔案和檔案夾，而當c是檔案的話，隻需要輸出檔案c即可。另外需要注意的是在建立檔案夾的時候，路徑上沒有的檔案夾都要建立出來，還有就是在給檔案添加内容時，路徑中沒有的檔案夾都要建立出來。論壇上這道題的高票解法都建立了一個自定義類，但是部落客一般不喜歡用自定義類來解題，而且感覺那些使用了自定義類的解法并沒有更簡潔易懂，是以這裡部落客就不建立自定義類了，而是使用兩個哈希表來做，其中dirs建立了路徑和其對應的包含所有檔案和檔案夾的集合之間的映射，files建立了檔案的路徑跟其内容之間的映射。

最開始時将根目錄"/"放入dirs中，然後看ls的實作方法，如果該路徑存在于files中，說明最後一個字元串是檔案，那麼我們将檔案名取出來傳回即可，如果不存在，說明最後一個字元串是檔案夾，那麼我們到dirs中取出該檔案夾内所有的東西傳回即可。再來看mkdir函數，我們的處理方法就是根據"/"來分隔分隔字元串，如果是Java，那麼直接用String自帶的split函數就好了，但是C++沒有Java那麼多自帶函數，是以隻能借助字元串流類來處理，處理方法就是将每一層的路徑分離出來，然後将該層的檔案或者檔案夾加入對應的集合中，注意的地方就是處理根目錄時，要先加上"/"，其他情況都是後加。下面來看addContentToFile函數，首先分離出路徑和檔案名，如果路徑為空，說明是根目錄，需要加上"/"，然後看這個路徑是否已經在dirs中存在，如果不存在，調用mkdir來建立該路徑，然後把檔案加入該路徑對應的集合中，再把内容加入該檔案路徑的映射中。最後的讀取檔案内容就相當簡單了，直接在files中傳回即可，參見代碼如下：

<a>class FileSystem {</a>

參考資料：

<a href="https://discuss.leetcode.com/topic/90250/c-fast-no-user-defined-types-needed" target="_blank">https://discuss.leetcode.com/topic/90250/c-fast-no-user-defined-types-needed</a>

，如需轉載請自行聯系原部落客。