{"id":6956,"date":"2020-06-20T22:31:46","date_gmt":"2020-06-21T05:31:46","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6956"},"modified":"2020-06-20T22:33:08","modified_gmt":"2020-06-21T05:33:08","slug":"leetcode-1487-making-file-names-unique","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1487-making-file-names-unique\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1487. Making File Names Unique"},"content":{"rendered":"\n

Given an array of strings names<\/code> of size n<\/code>. You will create n<\/code> folders in your file system such that<\/strong>, at the ith<\/code> minute, you will create a folder with the name names[i]<\/code>.<\/p>\n\n\n\n

Since two files cannot<\/strong> have the same name, if you enter a folder name which is previously used, the system will have a suffix addition to its name in the form of (k)<\/code>, where, k<\/code> is the smallest positive integer<\/strong> such that the obtained name remains unique.<\/p>\n\n\n\n

Return an array of strings of length n<\/code><\/em> where ans[i]<\/code> is the actual name the system will assign to the ith<\/code> folder when you create it.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> names = [\"pes\",\"fifa\",\"gta\",\"pes(2019)\"]\nOutput:<\/strong> [\"pes\",\"fifa\",\"gta\",\"pes(2019)\"]\nExplanation:<\/strong> Let's see how the file system creates folder names:\n\"pes\" --> not assigned before, remains \"pes\"\n\"fifa\" --> not assigned before, remains \"fifa\"\n\"gta\" --> not assigned before, remains \"gta\"\n\"pes(2019)\" --> not assigned before, remains \"pes(2019)\"\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> names = [\"gta\",\"gta(1)\",\"gta\",\"avalon\"]\nOutput:<\/strong> [\"gta\",\"gta(1)\",\"gta(2)\",\"avalon\"]\nExplanation:<\/strong> Let's see how the file system creates folder names:\n\"gta\" --> not assigned before, remains \"gta\"\n\"gta(1)\" --> not assigned before, remains \"gta(1)\"\n\"gta\" --> the name is reserved, system adds (k), since \"gta(1)\" is also reserved, systems put k = 2. it becomes \"gta(2)\"\n\"avalon\" --> not assigned before, remains \"avalon\"\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> names = [\"onepiece\",\"onepiece(1)\",\"onepiece(2)\",\"onepiece(3)\",\"onepiece\"]\nOutput:<\/strong> [\"onepiece\",\"onepiece(1)\",\"onepiece(2)\",\"onepiece(3)\",\"onepiece(4)\"]\nExplanation:<\/strong> When the last folder is created, the smallest positive valid k is 4, and it becomes \"onepiece(4)\".\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> names = [\"wano\",\"wano\",\"wano\",\"wano\"]\nOutput:<\/strong> [\"wano\",\"wano(1)\",\"wano(2)\",\"wano(3)\"]\nExplanation:<\/strong> Just increase the value of k each time you create folder \"wano\".\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> names = [\"kaido\",\"kaido(1)\",\"kaido\",\"kaido(1)\"]\nOutput:<\/strong> [\"kaido\",\"kaido(1)\",\"kaido(2)\",\"kaido(1)(1)\"]\nExplanation:<\/strong> Please note that system adds the suffix (k) to current name even it contained the same suffix before.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= names.length <= 5 * 10^4<\/code><\/li>
  • 1 <= names[i].length <= 20<\/code><\/li>
  • names[i]<\/code> consists of lower case English letters, digits and\/or round brackets.<\/li><\/ul>\n\n\n\n
    Solution: Hashtable<\/strong><\/h2>\n\n\n\n
    Use a hashtable to store the mapping form base_name to its next suffix index.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector getFolderNames(vector& names) {\n    vector ans;\n    unordered_map m; \/\/ base_name -> next suffix.\n    for (const string& name : names) {\n      string unique_name = name;\n      int j = m[name];\n      if (j > 0) {\n        while (m.count(unique_name = name + \"(\" + to_string(j++) + \")\"));    \n        m[name] = j;        \n      }\n      m[unique_name] = 1;\n      ans.push_back(unique_name);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i]. Since…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,4],"class_list":["post-6956","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6956","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6956"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6956\/revisions"}],"predecessor-version":[{"id":6958,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6956\/revisions\/6958"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6956"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6956"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6956"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}