保证文件名唯一

标签: 数组 哈希表 字符串

难度: Medium

给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。

由于两个文件 不能 共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的 最小正整数 。

返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。

示例 1：

输入：names = ["pes","fifa","gta","pes(2019)"]
输出：["pes","fifa","gta","pes(2019)"]
解释：文件系统将会这样创建文件名：
"pes" --> 之前未分配，仍为 "pes"
"fifa" --> 之前未分配，仍为 "fifa"
"gta" --> 之前未分配，仍为 "gta"
"pes(2019)" --> 之前未分配，仍为 "pes(2019)"

示例 2：

输入：names = ["gta","gta(1)","gta","avalon"]
输出：["gta","gta(1)","gta(2)","avalon"]
解释：文件系统将会这样创建文件名：
"gta" --> 之前未分配，仍为 "gta"
"gta(1)" --> 之前未分配，仍为 "gta(1)"
"gta" --> 文件名被占用，系统为该名称添加后缀 (k)，由于 "gta(1)" 也被占用，所以 k = 2 。实际创建的文件名为 "gta(2)" 。
"avalon" --> 之前未分配，仍为 "avalon"

示例 3：

输入：names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
输出：["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
解释：当创建最后一个文件夹时，最小的正有效 k 为 4 ，文件名变为 "onepiece(4)"。

示例 4：

输入：names = ["wano","wano","wano","wano"]
输出：["wano","wano(1)","wano(2)","wano(3)"]
解释：每次创建文件夹 "wano" 时，只需增加后缀中 k 的值即可。

示例 5：

输入：names = ["kaido","kaido(1)","kaido","kaido(1)"]
输出：["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
解释：注意，如果含后缀文件名被占用，那么系统也会按规则在名称后添加新的后缀 (k) 。

提示：

  • 1 <= names.length <= 5 * 10^4
  • 1 <= names[i].length <= 20
  • names[i] 由小写英文字母、数字和/或圆括号组成。

Submission

运行时间: 75 ms

内存: 30.4 MB

from collections import defaultdict
from typing import List

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        used_names = defaultdict(int)  # 用于跟踪已经使用过的文件名及其后缀版本的数量
        result = []
        
        for name in names:
            if name not in used_names or used_names[name] == 0:
                # 如果文件名尚未使用，或者其原始版本（没有后缀）尚未使用，则直接使用它
                result.append(name)
                used_names[name] += 1  # 增加该名称的使用计数
            else:
                # 如果文件名已经被使用，我们需要找到一个未被使用的后缀版本
                k = used_names[name]
                while True:
                    new_name = f"{name}({k})"
                    if new_name not in used_names:
                        result.append(new_name)
                        used_names[name] += 1  # 增加原始名称的使用计数（为下一个可能的重复做准备）
                        used_names[new_name] = 1  # 标记这个新的后缀版本为已使用
                        break
                    k += 1
                    
        return result

from collections import defaultdict
from typing import List

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        def get_unique_name(name, count):
            if count == 0:
                return name
            return get_unique_name(f"{name}({count})", count - 1)

        used_names = defaultdict(int)  # 字典用于跟踪已使用的名称及其“下一个可用后缀”的计数
        result = []
        
        for name in names:
            if name not in used_names:
                # 如果名称尚未使用，将其添加到结果中并设置计数为1（表示下一个重复需要后缀）
                result.append(name)
                used_names[name] = 1
            else:
                # 如果名称已使用，获取其“下一个可用后缀”的计数，并使用辅助函数生成唯一的名称
                count = used_names[name]
                unique_name = get_unique_name(name, count)
                result.append(unique_name)
                used_names[name] = count + 1  # 更新下一个重复需要的后缀计数
                used_names[unique_name] = 0  # 标记这个新的唯一名称为“尚未使用”，但实际上我们不会再次使用它，这只是一个占位符。
                
        return result

from collections import defaultdict
from typing import List

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        used_names = defaultdict(int)  # 字典用于跟踪已使用的名称及其后缀计数
        result = []
        
        for name in names:
            if not used_names[name]:
                # 如果名称尚未使用，将其添加到结果中并设置计数为1
                result.append(name)
                used_names[name] = 1
            else:
                # 如果名称已使用，增加后缀计数直到找到一个未使用的名称
                count = used_names[name]
                while True:
                    new_name = f"{name}({count})"
                    if new_name not in used_names or used_names[new_name] == 0:
                        result.append(new_name)
                        used_names[name] = count + 1  # 更新原始名称的后缀计数
                        used_names[new_name] = 1  # 标记新名称为已使用（对于可能的进一步重复）
                        break
                    count += 1
                    
        return result

Explain

此题解使用一个哈希表（defaultdict）来跟踪每个文件名以及其后缀形式的使用情况。对于每个输入的文件名，如果它尚未被使用过，直接使用它并在哈希表中做标记。如果已被使用，则通过循环增加后缀的编号，生成一个新的唯一文件名。使用格式'name(k)'，其中k是最小未被使用的正整数，确保文件名的唯一性。通过不断检查新生成的文件名是否被占用，直到找到一个未被使用的为止。

时间复杂度: O(n) 在平均情况下; O(n*k) 在最坏情况下，其中k是某个文件名的最大重复次数

空间复杂度: O(n)

from collections import defaultdict
from typing import List

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        used_names = defaultdict(int)  # 记录每个文件名及其后缀的使用次数
        result = []
        
        for name in names:
            if used_names[name] == 0:
                # 如果文件名未使用，直接添加到结果中
                result.append(name)
                used_names[name] += 1  # 标记为已使用
            else:
                # 文件名已使用，寻找新的未使用后缀
                count = used_names[name]
                while True:
                    new_name = f"{name}({count})"
                    if used_names[new_name] == 0:
                        result.append(new_name)
                        used_names[new_name] = 1  # 标记新名称为已使用
                        used_names[name] = count + 1  # 更新原名称后缀计数
                        break
                    count += 1
        
        return result

Explore

在此题解中，每个文件名（无论是原始的还是带后缀的）都作为哈希表的键。例如，'file'和'file(1)'在哈希表中是不同的键。这种设计可以避免将原始文件名和修改后的文件名混淆。因此不存在将它们视为同一个键的情况。当检查一个新文件名是否已使用时，会分别检查其作为原始名称和作为修改后名称的情况。

在Python中，使用`defaultdict`时可以通过传递一个类型（如`int`），默认将每个新键的值初始化为该类型的默认值。对于`int`类型，其默认值是`0`。因此，在`used_names`哈希表中，当首次引用一个文件名时，如果它之前未出现过，其计数自动初始化为`0`。这便于检查一个文件名是否首次使用，并在首次使用时将其计数设为`1`。

题解中的逻辑首先会将'pes(1)'作为一个独立的文件名处理并存储，此时'pes(1)'在哈希表中计数为1。当后续出现'pes'时，代码会检查'pes'是否已使用。如果'pes'未被使用，则直接添加'pes'并将其计数设为1。如果'pes'已使用，代码会尝试生成新的文件名，如'pes(1)'，'pes(2)'等。在这个例子中，由于'pes(1)'已经存在，代码会检测到这一点并尝试更高的后缀，比如'pes(2)'。这种处理确保了即使输入中包含形如'name(k)'的文件名，生成的文件名依然是唯一的。