Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1166.html

1166. Design File System

Level

Medium

Description

You are asked to design a file system which provides two functions:

  • createPath(path, 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.
  • get(path): Returns the value associated with a path or returns -1 if the path doesn’t exist.

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 two functions.

Please refer to the examples for clarifications.

Example 1:

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

Example 2:

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.

Constraints:

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

Solution

Create a class TreeNode that contains String path, int value and List<TreeNode> children. The objects of TreeNode are comparable using path, and all the elements in children are sorted in ascending order.

In class FileSystem, maintain a list of roots, which are of type TreeNode.

For the constructor, initialize the list of roots.

For createPath(path, value), remove the first / and split path into an array using /. For each element in the array, try to find the corresponding node. If a node in the middle is not found, then the node in the parent path does not exist, so return false. If a node at the last level is found, then the complete path already exists, so return false. When the end of the path is reached, create a new node using the path and the value, and a child node is added to its parent’s children.

For get(path), the logic is similar to createPath. At any step, the path must be available, or return -1 otherwise. After the end of the path is reached, obtain the value and return.

  • class FileSystem {
    List<TreeNode> roots;

    public FileSystem() {
        roots = new ArrayList<TreeNode>();
    }

    public boolean createPath(String path, int value) {
        if (path.charAt(0) == '/')
            path = path.substring(1);
        String[] array = path.split("/");
        int length = array.length;
        TreeNode tempNode = null;
        List<TreeNode> tempList = roots;
        for (int i = 0; i < length; i++) {
            String subPath = array[i];
            int index = binarySearch(tempList, subPath);
            if (index < 0 && i < length - 1 || index >= 0 && i == length - 1)
                return false;
            if (index >= 0) {
                tempNode = tempList.get(index);
                tempList = tempNode.getChildren();
            } else {
                TreeNode newNode = new TreeNode(subPath, value);
                if (tempNode == null) {
                    roots.add(newNode);
                    Collections.sort(roots);
                } else
                    tempNode.addChild(newNode);
            }
        }
        return true;
    }

    public int get(String path) {
        if (path.charAt(0) == '/')
            path = path.substring(1);
        String[] array = path.split("/");
        int length = array.length;
        TreeNode tempNode = null;
        List<TreeNode> tempList = roots;
        for (int i = 0; i < length; i++) {
            String subPath = array[i];
            int index = binarySearch(tempList, subPath);
            if (index < 0)
                return -1;
            else {
                tempNode = tempList.get(index);
                tempList = tempNode.getChildren();
            }
        }
        return tempNode.getValue();
    }

    public int binarySearch(List<TreeNode> list, String subPath) {
        int low = 0, high = list.size() - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            TreeNode temp = list.get(mid);
            String tempPath = temp.getPath();
            if (tempPath.compareTo(subPath) == 0)
                return mid;
            else if (tempPath.compareTo(subPath) < 0)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return -low - 1;
    }
}

class TreeNode implements Comparable<TreeNode> {
    private String path;
    private int value;
    private List<TreeNode> children;

    public TreeNode() {
        children = new ArrayList<TreeNode>();
    }

    public TreeNode(String path, int value) {
        this.path = path;
        this.value = value;
        children = new ArrayList<TreeNode>();
    }

    public String getPath() {
        return path;
    }

    public int getValue() {
        return value;
    }

    public List<TreeNode> getChildren() {
        return children;
    }

    public void addChild(TreeNode child) {
        children.add(child);
        Collections.sort(children);
    }

	public int compareTo(TreeNode node) {
		return this.path.compareTo(node.path);
	}
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * boolean param_1 = obj.createPath(path,value);
 * int param_2 = obj.get(path);
 */


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

class Trie {
    Map<String, Trie> children = new HashMap<>();
    int v;

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

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

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

    public FileSystem() {
    }

    public boolean createPath(String path, int value) {
        return trie.insert(path, value);
    }

    public int get(String path) {
        return trie.search(path);
    }
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * boolean param_1 = obj.createPath(path,value);
 * int param_2 = obj.get(path);
 */

  • // OJ: https://leetcode.com/problems/design-file-system/
// Time:
//      FileSystem: O(1)
//      createPath, get: O(P)
// Space: O(N)
class FileSystem {
    unordered_map<string, int> m;
public:
    FileSystem() {}
    bool createPath(string path, int value) {
        if (m.count(path)) return false;
        auto i = path.find_last_of("/");
        auto parent = path.substr(0, i);
        if (parent.size() && m.count(parent) == 0) return false;
        m[path] = value;
        return true;
    }
    int get(string path) {
        return m.count(path) ? m[path] : -1;
    }
};

  • class Trie:
    def __init__(self):
        self.children = {}
        self.v = 0

    def insert(self, w, v):
        node = self
        ps = w.split('/')
        for p in ps[1:-1]:
            if p not in node.children:
                return False
            node = node.children[p]
        if ps[-1] in node.children:
            return False
        node.children[ps[-1]] = Trie()
        node = node.children[ps[-1]]
        node.v = v
        return True

    def search(self, w):
        node = self
        for p in w.split('/')[1:]:
            if p not in node.children:
                return -1
            node = node.children[p]
        return node.v or -1


class FileSystem:
    def __init__(self):
        self.trie = Trie()

    def createPath(self, path: str, value: int) -> bool:
        return self.trie.insert(path, value)

    def get(self, path: str) -> int:
        return self.trie.search(path)


# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.createPath(path,value)
# param_2 = obj.get(path)



  • type Trie struct {
	children map[string]*Trie
	v        int
}

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

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

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

type FileSystem struct {
	trie *Trie
}

func Constructor() FileSystem {
	return FileSystem{newTrie()}
}

func (this *FileSystem) CreatePath(path string, value int) bool {
	return this.trie.insert(path, value)
}

func (this *FileSystem) Get(path string) int {
	return this.trie.search(path)
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.CreatePath(path,value);
 * param_2 := obj.Get(path);
 */

All Problems

All Solutions