leetcode/
longest_absolute_file_path.rs

1//! # 388. 文件的最长绝对路径
2//!
3//! 难度 中等
4//!
5//! 假设文件系统如下图所示：![](https://assets.leetcode.com/uploads/2020/08/28/mdir.jpg)
6//!
7//!
8//! 这里将 `dir` 作为根目录中的唯一目录。`dir` 包含两个子目录 `subdir1` 和 `subdir2` 。`subdir1` 包含文件 `file1.ext` 和子目录 `subsubdir1`；`subdir2` 包含子目录 `subsubdir2`，该子目录下包含文件 `file2.ext` 。
9//!
10//! 在文本格式中，如下所示(⟶表示制表符)：
11//!
12//! ```text
13//! dir
14//! ⟶ subdir1
15//! ⟶ ⟶ file1.ext
16//! ⟶ ⟶ subsubdir1
17//! ⟶ subdir2
18//! ⟶ ⟶ subsubdir2
19//! ⟶ ⟶ ⟶ file2.ext
20//! ```
21//! 如果是代码表示，上面的文件系统可以写为 `"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"` 。`'\n'` 和 `'\t'` 分别是换行符和制表符。
22//!
23//! 文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 `'/'` 连接。上面例子中，指向 `file2.ext` 的绝对路径是 `"dir/subdir2/subsubdir2/file2.ext"` 。每个目录名由字母、数字和/或空格组成，每个文件名遵循 `name.extension` 的格式，其中名称和扩展名由字母、数字和/或空格组成。
24//!
25//! 给定一个以上述格式表示文件系统的字符串 `input` ，返回文件系统中 **指向文件的最长绝对路径** 的长度。 如果系统中没有文件，返回 `0`。
26//!
27//!
28//! ## 示例 1：
29//!
30//! ![](https://assets.leetcode.com/uploads/2020/08/28/dir1.jpg)
31//!
32//! ```text
33//! 输入：input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
34//! 输出：20
35//! 解释：只有一个文件，绝对路径为 "dir/subdir2/file.ext" ，路径长度 20
36//! 路径 "dir/subdir1" 不含任何文件
37//! ```
38//!
39//! ## 示例 2：
40//!
41//! ![](https://assets.leetcode.com/uploads/2020/08/28/dir2.jpg)
42//!
43//! ```text
44//! 输入：input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
45//! 输出：32
46//! 解释：存在两个文件：
47//! "dir/subdir1/file1.ext" ，路径长度 21
48//! "dir/subdir2/subsubdir2/file2.ext" ，路径长度 32
49//! 返回 32 ，因为这是最长的路径
50//! ```
51//!
52//! ## 示例 3：
53//!
54//! ```text
55//! 输入：input = "a"
56//! 输出：0
57//! 解释：不存在任何文件
58//! ```
59//!
60//! ## 示例 4：
61//!
62//! ```text
63//! 输入：input = "file1.txt\nfile2.txt\nlongfile.txt"
64//! 输出：12
65//! 解释：根目录下有 3 个文件。
66//! 因为根目录中任何东西的绝对路径只是名称本身，所以答案是 "longfile.txt" ，路径长度为 12
67//! ```
68//!
69//! ## 提示：
70//!
71//! * 1 <= input.length <= 10<sup>4</sup>
72//! * `input` 可能包含小写或大写的英文字母，一个换行符 `'\n'`，一个指表符 `'\t'`，一个点 `'.'`，一个空格 `' '`，和数字。
73//!
74//! See [leetcode](https://leetcode-cn.com/problems/longest-absolute-file-path/)
75
76pub struct Solution;
77
78impl Solution {
79
80    /// 用 Rust 的 `Iterator` 写函数式的解法。
81    ///
82    /// 先把输入拆分，因为每个片断都包含了文件名，路径深度和目录文件类型，对片断预处理。因为字符串表示是顺序表示的，所以前后之间是需要处理的。详细步骤说明：
83    ///
84    /// * 按 `\n` 切分输入 `split('\n')`
85    /// * 把每个 `\t\tfile_name` 映射成 `(level, file_name_length, is_file)`，这里的 `level` 从 `0` 开始（即根目录 level 为 `0`）
86    ///     * 找到第一个不是 `\t` 的字符的位置，position 表示 `\t` 个数，即 level 层级，剩下的即文件名，我们取其长度即可，同时判断是否为文件（文件名中是否带 `.`）
87    ///     * 如果没有 `\t` 说明是在根目录下的，即 `level` 为 `0`
88    /// * 计算每一个目录/文件名的长度（根据上一步生成的 tuple），因为每次分析都需要用到之前的路径在哪一层，所以需要用到 state 状态（栈），计算结果是每个目录/文件的长度，所以用 `scan`
89    ///     * 初始状态是 `[]`，这里的状态表示**上一次**的父目录的绝对路径长度，即 `[level_0_len, level_1_len, level_2_len, ...]`
90    ///     * 进入到当前目录/文件，需要弹出上一次的父目录，直到 `parents` 里只剩当前目录/文件的父级（这里用 `split_off(at)` 来简化多次 `pop()`
91    ///     * 当前级别的目录/文件的长度就是剩下的 `parents` 里最后一个父目录的绝对路径长度和 + 当前文件名长度
92    ///     * 如果当前是目录，则当前目录长度 `push` 入栈，注意需要 `+ 1` 表示算上 `/`
93    ///     * `scan` 函数的参数函数里，返回 `(abs_len, is_file`) （注：`scan` 函数相当于是 `fold` + `map`，或者说 `map` 带了个 state 状态）
94    /// * 经过上一步，转换的结果已经变成 `(abs_len, is_file)` 了，只要过滤掉不是文件的项
95    /// * 然后找出 `max` 就是结果了
96    ///
97    /// 这里除了 `scan` 中每一步过程中需要更新 `parents` 这个状态，其它地方没有任何的 mutable 变量。函数式编程的方式逻辑非常清晰，代码写起来也非常方便，可读性高，加上 immutable 使得安全性也非常好。关键是在 Rust 里用函数式的方法几乎不损失性能。
98    pub fn length_longest_path(input: String) -> i32 {
99        input
100            .split('\n')
101            .map(|s| {
102                s.find(|c| c != '\t')
103                .map(|n| (n, s.len() - n, (&s[n..]).chars().any(|c| c == '.')))
104                .unwrap_or_else(|| (0, s.len(), s.chars().any(|c| c == '.')))
105            })
106            .scan(vec![], |parents, (level, s_len, is_file)| {
107                if level < parents.len() {
108                    let _ = parents.split_off(level); // pop until parent level
109                }
110
111                let abs_len = s_len + parents.last().unwrap_or(&0);
112
113                if !is_file {
114                    parents.push(abs_len + 1);
115                }
116
117                Some((abs_len, is_file))
118            })
119            .filter(|(_, is_file)| *is_file)
120            .map(|(n, _)| n)
121            .max()
122            .unwrap_or(0) as i32
123    }
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129
130    #[test]
131    fn test() {
132        let cases = vec![
133            (20, "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"),
134            (32, "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"),
135            (0, "a"),
136            (5, "a.txt"),
137            (5, "b.t\na.txt"),
138            (12, "file1.txt\nfile2.txt\nlongfile.txt"),
139            (16, "dir\n        file.txt"),
140            (14, "a\n\tb1\n\t\tf1.txt\n\taaaaa\n\t\tf2.txt"),
141            (29, "a\n\taa\n\t\taaa\n\t\t\tfile1.txt\naaaaaaaaaaaaaaaaaaaaa\n\tsth.png"),
142            (10, "a\n\tb\n\t\tc.txt\n\taaaa.txt"),
143        ];
144
145        for (expect, input) in cases {
146            assert_eq!(expect, Solution::length_longest_path(input.into()));
147        }
148    }
149}
leetcode/longest_absolute_file_path.rs

leetcode/
longest_absolute_file_path.rs
