Solution Review: Folder Count
See the solution for the problem challenge.
We'll cover the following...
Solution
#include <iostream>#include <vector>#include <unordered_map>using namespace std;// Definition of a trienodeclass TrieNode{public:// map which stores the pointers from// folder names to the children nodesunordered_map<string, TrieNode*> children;};class FileSystem{public:TrieNode * root;FileSystem(){root = new TrieNode();}// inserts the directory path in the file systembool directoryInsert(string directory){int insertions = 0;// point the current node to the root of the trieTrieNode *curr = root;// Iterate over the folder namesfor (string singleFolder: pathToStringList(directory)){// If the folder name is not found in trie// create a new one// else traverse down the pathif (curr->children.find(singleFolder) == curr->children.end()){TrieNode *childDirectory = new TrieNode();curr->children[singleFolder] = childDirectory;insertions++;}curr = curr->children[singleFolder];}return insertions > 0;}int directoryMatchCount(string directory){// intialize match count as zeroint matchCount = 0;// point the current node to the root of the trieTrieNode *curr = root;// Iterate over the folder namesfor (string singleFolder: pathToStringList(directory)){// If the folder name is not found in trie// it means directory does not exists// return matchCountif (curr->children.find(singleFolder) == curr->children.end()){return matchCount;}curr = curr->children[singleFolder];matchCount++;}// if all folders in directory path are// found return matchCountreturn matchCount;}// converts a directory path to// list of folder names// ex : (/home/mike/profile =>["home", "mike", "profile"])vector<string> pathToStringList(string path){path = path.substr(1);vector<string> folders;string folderName = "";for (auto p: path){if (p == '/'){folders.push_back(folderName);folderName = "";}elsefolderName += p;}folders.push_back(folderName);return folders;}};
Intuition
The problem is just an extension of the first problem of the chapter. The problem requires us to create a directory structure and count how many folders match the given directory path input. We can also use a trie structure similar to the first lesson. For matching, we'll start from the root folder and keep counting up to the first unmatched folder name.
Algorithm
We can implement the required functions using the following algorithm.
directoryInsert
We can break each path into a list of words, with each word representing one folder. This list of words can now be inserted into the trie to represent the complete directory structure.
directoryMatchCount
Similar to step one, we can break the path into a list of words, with each word representing one folder. This list of words can be used to traverse the trie. The value of matchCount
is incremented when we move from one folder to the other in the directory. We'll keep traversing the trie until we can no longer find the current folder. We can stop traversing the trie as soon as a path mismatch happens and return the value matchCount
as the answer.
Visualization
The picture below represents the insertion and counting procedure.
Complexity analysis
Variables
Number of directory paths in the input =
. ...