Find length of longest absolute file path

Suppose we represent our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Note:

The name of a file contains at least a period and an extension.

The name of a directory or sub-directory will not contain a period.


Example:

Input:  str="dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
Output: 32

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int lengthLongestPath(string input)
{
    stringstream ss(input);
    string line;
    unordered_map<intintmap = {{00}};
    int res = 0;

    while (getline(ssline'\n'))
    {
        auto tab = line.find_last_of('\t');
        int level = tab == string::npos ? 0 : tab + 1;
        int len = line.substr(level).length();
        if (line.find('.') != string::npos)
        {
            res = max(resmap[level] + len);
        }
        else
        {
            map[level + 1] = map[level] + len + 1;
        }
    }
    return res;
}

int main()
{
    string str = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\t
subdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";

    cout << lengthLongestPath(str);

    return 0;
}


No comments:

Post a Comment