【MEDIUM】Longest Absolute File Path

发布于: 2019-01-04 22:49
阅读: 66
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/longest-absolute-file-path/

Suppose we abstract 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 subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 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 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 . and an extension.
  • The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

分析过程

  • 输入:一组树状结构的路径
  • 输出:最长路径
  • 思路:
    • 题目要求的是最长路径,而且必须是文件的最长路径,目录不算。因此只要遍历一遍,取得所有文件(路径包含.)的绝对路径作比较就可以了。
    • 由于每层路径都用\t缩进,因此用\t可以直接拿到路径的深度。用一个栈当状态机,深度增加时候压栈,减少或相同时,需要把旧的弹出,把新的再压栈。
    • 深度减小时有可能一下子减少好几层,因此用while循环连续弹出。暂不考虑数据异常一下子增加好几层的情况。
    • 如果是文件就把栈 join 起来,就能拿到绝对路径了,最后作比较输出即可。

解决方法

class Solution {
    func lengthLongestPath(_ input: String) -> Int {
        let paths = input.components(separatedBy: "\n")
        var longestPath = ""
        
        // 用栈用来保存当前的路径
        var pathStack = Array<String>()
        
        paths.forEach { path in
            // 用 \t 的个数来计算当前路径的深度
            let level = path.components(separatedBy: "\t").count
            // 去掉 \t
            let path = path.replacingOccurrences(of: "\t", with: "")
            // 根据当前路径深度和栈的深度不同来处理栈
            if level > pathStack.count {
                // 暂不考虑输入异常,一下子缩进好几层的情况
                pathStack.append(path)
            } else if level == pathStack.count {
                _ = pathStack.popLast()
                pathStack.append(path)
            } else {
                // 有可能一下子退出好几层,这里需要根据退出的层数都弹出
                while level <= pathStack.count {
                    _ = pathStack.popLast()
                }
                pathStack.append(path)
            }
            // 包含.代表是文件
            if path.contains(".")  {
                // 取得完整路径判断是不是最长,更新最长路径
                let fullPath = pathStack.joined(separator: "/")
                if fullPath.count > longestPath.count {
                    longestPath = fullPath
                }
            }
        }
        
        return longestPath.count
    }
}

Thanks for reading.

All the best wishes for you! 💕