1487-保证文件名唯一

给你一个长度为 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] 由小写英文字母、数字和/或圆括号组成。

方法一：哈希表

对于需要被创建的文件名 name，如果文件系统中不存在名为 name 的文件夹，那么直接创建即可，否则我们需要从 k=1 开始，尝试使用添加后缀 k 的新文件名创建新文件夹。

使用哈希表 index 记录已创建的文件夹的下一后缀序号，遍历 names 数组，记当前遍历的文件名为 name：

• 如果 name 不在哈希表中，那么说明文件系统不存在名为 name 的文件夹，我们直接创建该文件夹，并且记录对应文件夹的下一后缀序号为 1。

• 如果 name 在哈希表中，那么说明文件系统已经存在名为 name 的文件夹，我们在哈希表找到 name 的下一后缀序号 k，逐一尝试直到添加后缀 k 的新文件名不存在于哈希表中，然后创建该文件夹。需要注意的是，创建该文件夹后，有两个文件名的下一后缀序号需要修改，首先文件名 name 的下一后缀序号为 k+1，其次，文件名 name 添加后缀 k 的新文件名的下一后缀序号为 1。

[sol1-Python3]

class Solution:
    def getFolderNames(self, names: List[str]) -> List[str]:
        ans = []
        index = {}
        for name in names:
            if name not in index:
                ans.append(name)
                index[name] = 1
            else:
                k = index[name]
                while name + '(' + str(k) + ')' in index:
                    k += 1
                t = name + '(' + str(k) + ')'
                ans.append(t)
                index[name] = k + 1
                index[t] = 1
        return ans

[sol1-C++]

class Solution {
public:
    string addSuffix(string name, int k) {
        return name + "(" + to_string(k) + ")";
    }

    vector<string> getFolderNames(vector<string>& names) {
        unordered_map<string, int> index;
        vector<string> res;
        for (const auto &name : names) {
            if (!index.count(name)) {
                res.push_back(name);
                index[name] = 1;
            } else {
                int k = index[name];
                while (index.count(addSuffix(name, k))) {
                    k++;
                }
                res.push_back(addSuffix(name, k));
                index[name] = k + 1;
                index[addSuffix(name, k)] = 1;
            }
        }
        return res;
    }
};

[sol1-Java]

class Solution {
    public String[] getFolderNames(String[] names) {
        Map<String, Integer> index = new HashMap<String, Integer>();
        int n = names.length;
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            String name = names[i];
            if (!index.containsKey(name)) {
                res[i] = name;
                index.put(name, 1);
            } else {
                int k = index.get(name);
                while (index.containsKey(addSuffix(name, k))) {
                    k++;
                }
                res[i] = addSuffix(name, k);
                index.put(name, k + 1);
                index.put(addSuffix(name, k), 1);
            }
        }
        return res;
    }

    public String addSuffix(String name, int k) {
        return name + "(" + k + ")";
    }
}

[sol1-C#]

public class Solution {
    public string[] GetFolderNames(string[] names) {
        IDictionary<string, int> index = new Dictionary<string, int>();
        int n = names.Length;
        string[] res = new string[n];
        for (int i = 0; i < n; i++) {
            string name = names[i];
            if (!index.ContainsKey(name)) {
                res[i] = name;
                index.Add(name, 1);
            } else {
                int k = index[name];
                while (index.ContainsKey(AddSuffix(name, k))) {
                    k++;
                }
                res[i] = AddSuffix(name, k);
                index[name] = k + 1;
                index.Add(AddSuffix(name, k), 1);
            }
        }
        return res;
    }

    public string AddSuffix(string name, int k) {
        return name + "(" + k + ")";
    }
}

[sol1-C]

typedef struct {
    char *key;
    int val;
    UT_hash_handle hh;
} HashItem;

HashItem *hashFindItem(HashItem **obj, char *key) {
    HashItem *pEntry = NULL;
    HASH_FIND_STR(*obj, key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, char *key, int val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = (char *)calloc(sizeof(char), strlen(key) + 1);
    strcpy(pEntry->key, key);
    pEntry->val = val;
    HASH_ADD_STR(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem **obj, const char *key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        hashAddItem(obj, key, val);
    } else {
        pEntry->val = val;
    }
    return true;
}

int hashGetItem(HashItem **obj, char *key, int defaultVal) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return defaultVal;
    }
    return pEntry->val;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr->key);
        free(curr);             
    }
}

char ** getFolderNames(char ** names, int namesSize, int* returnSize) {
    HashItem *index = NULL;
    char **res = (char **)calloc(sizeof(char *), namesSize);
    int pos = 0;
    for (int i = 0; i < namesSize; i++) {
        if (!hashFindItem(&index, names[i])) {
            res[pos] = (char *)calloc(sizeof(char), strlen(names[i]) + 1);
            strcpy(res[pos], names[i]);
            pos++;
            hashAddItem(&index, names[i], 1);
        } else {
            int k = hashGetItem(&index, names[i], 0);
            char str[strlen(names[i]) + 16];
            sprintf(str, "%s(%d)", names[i], k);
            while (hashFindItem(&index, str)) {
                k++;
                sprintf(str, "%s(%d)", names[i], k);
            }
            res[pos] = (char *)calloc(sizeof(char), strlen(str) + 1);
            strcpy(res[pos], str);
            pos++;
            hashSetItem(&index, names[i], k + 1);
            hashAddItem(&index, str, 1);
        }
    }
    *returnSize = pos;
    hashFree(&index);
    return res;
}

[sol1-JavaScript]

var getFolderNames = function(names) {
    const index = new Map();
    const n = names.length;
    const res = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        const name = names[i];
        if (!index.has(name)) {
            res[i] = name;
            index.set(name, 1);
        } else {
            let k = index.get(name);
            while (index.has(addSuffix(name, k))) {
                k++;
            }
            res[i] = addSuffix(name, k);
            index.set(name, k + 1);
            index.set(addSuffix(name, k), 1);
        }
    }
    return res;
}

const addSuffix = (name, k) => {
    return name + "(" + k + ")";
};

[sol1-Golang]

func getFolderNames(names []string) []string {
    ans := make([]string, len(names))
    index := map[string]int{}
    for p, name := range names {
        i := index[name]
        if i == 0 {
            index[name] = 1
            ans[p] = name
            continue
        }
        for index[name+"("+strconv.Itoa(i)+")"] > 0 {
            i++
        }
        t := name + "(" + strconv.Itoa(i) + ")"
        ans[p] = t
        index[name] = i + 1
        index[t] = 1
    }
    return ans
}

复杂度分析

• 时间复杂度：O(\sum_{i=0}^{n-1} m_i)，其中 m_i 表示字符串 names}[i] 的长度，n 表示数组 names 的长度。外层循环每次运行时间为 O(m_i)，总时间复杂度为 O(\sum_{i=0}^{n-1} m_i)；内层循环的总运行次数不超过 n 次，总时间复杂度为 O(\sum_{i=0}^{n-1} m_i)。

• 空间复杂度：O(\sum_{i=0}^{n-1}{m_i})。保存哈希表需要 O(\sum_{i=0}^{n-1}{m_i}) 的空间。