1487. 保证文件名唯一

题目链接：1487. 保证文件名唯一

方法：哈希表

解题思路

设文件名s对应的出现次数为\(cnt[s]\)，当前需要创建的文件夹名为\(names[i]\)，会有两种情况：

1. 当前文件夹名为出现过，则\(cnt[names[i]] = 1\)；
2. 当前文件名之前出现过，则更新其后缀名\((cnt[names[i]])\)到最新，然后创建新文件夹\(s\)，并\(cnt[s] ++\)。

代码

class Solution {
public:
    vector<string> getFolderNames(vector<string>& names) {
        unordered_map<string, int> cnt;
        for (auto &str : names) {
            int idx = cnt[str];
            if (idx) {
                // cnt 表示的是上一次处理文件名为cnt[str]的下一个后缀，
                // 但中间可能被其他文件夹名为str(idx)的占用，所以要更新。
                while (cnt[str + "(" + to_string(idx) + ")"]) { 
                    idx ++ ;
                    cnt[str] ++ ;
                }
                cnt[str] ++ ;
                str += "(" + to_string(idx) + ")";
                cnt[str] ++ ;
            } else {
                cnt[str] = 1;
            }
        }
        return names;
    }
};

复杂度分析

时间复杂度：\(O(L)\)，\(L\)为所有文件名长度之和；
空间复杂度：\(O(L)\)。