LeetCode 1166 Design File System

<div>

You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string "" and "/" are not.

Implement the FileSystem class:

bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn't exist.
int get(string path) Returns the value associated with path or returns -1 if the path doesn't exist.

Example 1:

<pre>Input: ["FileSystem","createPath","get"] [[],["/a",1],["/a"]] Output: [null,true,1] Explanation: FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true fileSystem.get("/a"); // return 1 </pre>

Example 2:

<pre>Input: ["FileSystem","createPath","createPath","get","createPath","get"] [[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]] Output: [null,true,true,2,false,-1] Explanation: FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/leet", 1); // return true fileSystem.createPath("/leet/code", 2); // return true fileSystem.get("/leet/code"); // return 2 fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist. fileSystem.get("/c"); // return -1 because this path doesn't exist. </pre>

Constraints:

The number of calls to the two functions is less than or equal to 10<sup>4</sup> in total.
2 <= path.length <= 100
1 <= value <= 10<sup>9</sup>

</div>

题目大意：

设计文件系统，支持创建路径，路径含key, value

Trie解题思路：

用Trie, is_end变成key, value

解题步骤：

N/A

注意事项：

遍历用1开始，因为首个/前面是空字符串

Python代码：

class FileSystem(TestCases):

    def __init__(self):
        self.head = TrieNode('')

    def createPath(self, path: str, value: int) -> bool:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                if i == len(segments) - 1: # match all the previous segments
                    it.children[segment] = TrieNode(segment)
                else:
                    return False
            it = it.children[segment]
        if it.value != -1: # exists
            return False
        it.value = value
        return True

    def get(self, path: str) -> int:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                return -1
            it = it.children[segment]
        return it.value

class TrieNode:

    def __init__(self, name):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.name = name
        self.value = -1

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

算法II HashMap解题思路：

用前缀法

Python代码：

class FileSystem2(TestCases):

    def __init__(self):
        self.path_to_val = defaultdict()

    def createPath(self, path: str, value: int) -> bool:

        if path == "/" or len(path) == 0 or path in self.path_to_val:
            return False

        # search from the right
        parent = path[:path.rfind('/')]
        if len(parent) > 1 and parent not in self.path_to_val:
            return False

        self.path_to_val[path] = value
        return True

    def get(self, path: str) -> int:
        return self.path_to_val.get(path, -1)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)