LeetCode 1166. 设计文件系统
题目描述
题意分析
维护一个路径到整数值的映射，支持创建和查询。创建只能新增尚不存在的完整路径，并且它的直接父路径必须已经存在；创建成功返回
true，路径重复或缺少父路径则返回false。查询只返回指定完整路径保存的值，不存在时返回
-1。本题不要求列出目录、读取文件内容或自动创建中间目录，创建失败也不能覆盖旧值或留下新路径。
解法：哈希表记录路径
核心思路
[!blue]
这两个接口都以完整路径为单位，哈希表保存完整路径和值就能完成查找。父子关系可以从路径文本恢复，不需要为了查询一个键额外构造目录树或保存孩子列表。
直接父路径是最后一个斜杠之前的部分。创建前先检查目标键是否已存在，再截取并检查直接父键；不能仅检查某个更远的祖先，否则会跳过尚未创建的中间层级。
一级路径的最后一个斜杠在开头，截出的父串为空。代码统一把它映射成预置的根哨兵
/，这样一级创建也能沿用相同的父路径存在性检查。哨兵只用于表示根存在，不是一次自动创建了任意目录层级。只有查重和父路径检查都通过，才将新路径和值写入表中。父路径在之前创建时也已经检查过自己的父路径，因此这个规则递推保证所有已保存的非根路径都有完整的祖先链；失败时保持状态不变。查询直接使用哈希表的缺省值即可。
解题步骤
- 构造空哈希表，预先放入根哨兵
/。- 创建时先检查完整路径是否已存在，已存在就返回
false。- 找到最后一个斜杠，取其前面的父路径；空父串统一映射为根。
- 父路径不存在时返回
false；存在才写入新值并返回true。- 查询时按完整路径取值，没有对应键就返回
-1。
代码实现
class FileSystem {
private final Map<String, Integer> values;
public FileSystem() {
// 根作为哨兵预置，让一级路径的父检查自然命中。
this.values = new HashMap<>();
values.put("/", -1);
}
public boolean createPath(String path, int value) {
if (values.containsKey(path)) {
return false;
}
// 父路径是最后一个 '/' 之前的部分；一级路径截出空串，映射回根。
int idx = path.lastIndexOf('/');
String parent = path.substring(0, idx);
if (parent.isEmpty()) {
parent = "/";
}
if (!values.containsKey(parent)) {
return false;
}
// 查重和父路径验证都通过后，才真正创建路径。
values.put(path, value);
return true;
}
public int get(String path) {
return values.getOrDefault(path, -1);
}
}
import "strings"
type FileSystem struct {
values map[string]int
}
func Constructor() FileSystem {
// 根作为哨兵预置，让一级路径的父检查自然命中。
return FileSystem{
values: map[string]int{"/": -1},
}
}
func (fs *FileSystem) CreatePath(path string, value int) bool {
if _, ok := fs.values[path]; ok {
return false
}
// 父路径是最后一个 '/' 之前的部分；一级路径截出空串，映射回根。
idx := strings.LastIndex(path, "/")
parent := path[:idx]
if parent == "" {
parent = "/"
}
if _, ok := fs.values[parent]; !ok {
return false
}
// 查重和父路径验证都通过后，才真正创建路径。
fs.values[path] = value
return true
}
func (fs *FileSystem) Get(path string) int {
if v, ok := fs.values[path]; ok {
return v
}
return -1
}
复杂度分析
- 时间复杂度：每次操作期望 $O(L)$，
L为输入路径长度，包含字符串哈希、比较与创建时的父路径提取。- 空间复杂度：持久存储为 $O(S)$，
S是已保存路径的总长度；创建操作还可能产生长度为 $O(L)$ 的临时父路径。
关键点总结
[!green]
- 完整路径查表已满足接口，只检查直接父路径即可维护祖先存在关系。
- 根哨兵将一级路径与深层路径的父检查统一起来。
- 路径存在性检查与写入分开，所有失败分支都应保持表内容不变。
易错点总结
[!yellow]
- 一级路径的空父串没有映射到根，会错误拒绝本应可以创建的一级节点。
- 用第一个斜杠而不是最后一个斜杠截取父路径，会把深层路径直接当成根的孩子。
- 先写入再检查父路径，返回失败后仍留下不合法记录。
- 已存在的路径直接覆盖新值，违背创建接口的失败语义。
- 只检查字符串前缀是否存在，而不按完整父路径查键，会把名字相似的路径误认成祖先。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 588. 设计内存文件系统 | 困难 | 本题路径只关联值且创建时检查父目录，原题进一步区分文件目录并支持内容与列表操作。 |
| 208. 实现 Trie (前缀树) | 中等 | 按路径组件逐层定位类似Trie，组件作为键而不是单个字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！