Solution Review: Folder Count

See the solution for the problem challenge.

Solution

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Definition of a trienode
class TrieNode
{
public:
// map which stores the pointers from
// folder names to the children nodes
unordered_map<string, TrieNode*> children;
};
class FileSystem
{
public:
TrieNode * root;
FileSystem()
{
root = new TrieNode();
}
// inserts the directory path in the file system
bool directoryInsert(string directory)
{
int insertions = 0;
// point the current node to the root of the trie
TrieNode *curr = root;
// Iterate over the folder names
for (string singleFolder: pathToStringList(directory))
{
// If the folder name is not found in trie
// create a new one
// else traverse down the path
if (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 zero
int matchCount = 0;
// point the current node to the root of the trie
TrieNode *curr = root;
// Iterate over the folder names
for (string singleFolder: pathToStringList(directory))
{
// If the folder name is not found in trie
// it means directory does not exists
// return matchCount
if (curr->children.find(singleFolder) == curr->children.end())
{
return matchCount;
}
curr = curr->children[singleFolder];
matchCount++;
}
// if all folders in directory path are
// found return matchCount
return 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 = "";
}
else
folderName += p;
}
folders.push_back(folderName);
return folders;
}
};
Solution for problem challenge in C++

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 =NN. ...

Access this course and 1400+ top-rated courses and projects.