LeetCode 1487. 保证文件名唯一

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
数组 字符串 哈希表

题目描述

✅ 1487. 保证文件名唯一

image-20260929084840705

image-20260929084840847

题意分析

按输入顺序创建文件夹。如果请求的完整名称尚未被使用，就直接采用；如果已经被占用，就在这个名称后追加 (k)，其中 k 是能使新名称未占用的最小正整数。

返回每次实际创建的名称。先前直接采用的名称和自动生成的名称都算占用；输入名称中已有的括号、数字也是名称本身的一部分，不能解析后替换它们。

解法：哈希表 + 后缀探测起点

核心思路

[!blue]

同一个基础名称反复冲突时，如果每次从后缀一开始查，会不断重试已知被占用的位置。用 nextSuffix 同时承担两件事：键是否存在表示完整名称是否已经占用，值记录该名称下次冲突时从哪个后缀开始探测。

新名称直接登记，探测起点设为一。已有名称冲突时，从它保存的 k 开始构造 name(k)，只要这个完整候选仍在表中，就继续增加后缀。第一个不在表中的候选就是本次可用结果。

保存的起点保证更小后缀已经被占用，且名称不会被释放，因此跳过它们不会错过更小答案。但起点本身不一定空闲：在此前两次请求之间，其他输入可能直接创建了它。所以仍需要循环检查真实占用状态。

找到可用后缀后，把基础名称的起点推进到 k + 1，并把新生成的完整名称也登记为占用、初始探测值为一。这样后续无论请求基础名称，还是直接请求这个生成名，都能正确处理。

每个基础名称的探测位置只向前走；同一个失败候选不会被它重复检查。一个标准后缀候选又唯一对应其最后一段 (k) 前面的基础名，所以全部失败探测可归到已占用名称上，避免平方级重复扫描。

解题步骤

  1. 创建空名称表及等长结果数组，依次处理输入。
  2. 完整名称未占用时直接输出，登记它的下一后缀为一。
  3. 名称已占用时，从保存的后缀开始逐个检查完整候选。
  4. 输出首个未占用候选，推进基础名的后缀记录。
  5. 同时登记新生成名，继续处理后续请求。

代码实现

class Solution {
    public String[] getFolderNames(String[] names) {
        Map<String, Integer> nextSuffix = new HashMap<>();
        String[] answer = new String[names.length];

        for (int i = 0; i < names.length; i++) {
            String name = names[i];

            if (!nextSuffix.containsKey(name)) {
                answer[i] = name;
                nextSuffix.put(name, 1);
                continue;
            }

            // 记录值只是探测起点，仍需检查后缀名称是否被占用。
            int suffix = nextSuffix.get(name);
            String candidate = name + "(" + suffix + ")";

            while (nextSuffix.containsKey(candidate)) {
                suffix++;
                candidate = name + "(" + suffix + ")";
            }

            answer[i] = candidate;
            // 推进当前基础名的探测起点，避免下次从头检查。
            nextSuffix.put(name, suffix + 1);
            // 生成名本身也属于已占用的完整名称。
            nextSuffix.put(candidate, 1);
        }

        return answer;
    }
}

import "strconv"

func getFolderNames(names []string) []string {
    nextSuffix := make(map[string]int)
    answer := make([]string, len(names))

    for i, name := range names {
        suffix, exists := nextSuffix[name]
        if !exists {
            answer[i] = name
            nextSuffix[name] = 1
            continue
        }

        // 记录值只是探测起点，仍需检查后缀名称是否被占用。
        candidate := name + "(" + strconv.Itoa(suffix) + ")"
        for {
            if _, occupied := nextSuffix[candidate]; !occupied {
                break
            }
            suffix++
            candidate = name + "(" + strconv.Itoa(suffix) + ")"
        }

        answer[i] = candidate
        // 推进当前基础名的探测起点，避免下次从头检查。
        nextSuffix[name] = suffix + 1
        // 生成名本身也属于已占用的完整名称。
        nextSuffix[candidate] = 1
    }
    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(nL)$，其中 $n$ 是请求数量，$L$ 是处理后名称的长度上界。探测总次数为线性级，每次构造及哈希字符串需要 $O(L)$。
  • 空间复杂度：$O(nL)$，用于已占用名称、后缀进度和结果字符串。

关键点总结

[!green]

  • 完整名称判断占用，基础名称记录后缀进度，两者由同一张表保存。
  • 进度表示无需再看更小后缀，不代表当前候选必定空闲。
  • 生成名本身也是新的完整名称，需要登记。
  • 按序处理、后缀递增探测，保证每一步得到当时最小的可用编号。

易错点总结

[!yellow]

  • 把记录起点当成保证可用，会与后来直接创建的名字冲突。
  • 只更新基础名而不登记生成名，后续无法识别实际已经存在的文件夹。
  • 每次冲突都从一开始，会重复探测大量已知占用后缀。
  • 擅自解析或改写输入原有括号，会改变名称本身，应该在完整原名后追加新后缀。

相似题目

题目 难度 关联与区别
945. 使数组唯一的最小增量 中等 同样遇冲突后寻找下一个可用结果，本题保留输入次序并在完整文件名空间中检查后缀冲突。
2336. 无限集中的最小数字 中等 同样缓存下一可用编号避免从头重试，本题每个基础文件名有自己的候选后缀序列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/33782512
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！