This is the 27th day of my participation in the First Challenge 2022

The title

Ensure that the file name is unique

You are given a string array names of length N. You will create n folders in the file system: at minute I, create a folder named Names [I].

Two files cannot share the same file name. Therefore, if the file name used for the new folder is already occupied, the system suffixes the file name of the new folder in the form of (k), where K is the minimum positive integer to ensure that the file name is unique.

Returns an array of strings of length N, where ans[I] is the actual name assigned to the i-th folder when it is created.

 

Example 1:

Input: names = [" pes ", "FIFA," "gta", "pes (2019)"] output: [" pes ", "FIFA", "gta", "pes (2019)"] : file system will create the file name like this: "Pes" --> previously not assigned, still "PES" "FIFA" --> previously not assigned, still "FIFA" "GTA" --> Previously not assigned, still "PES (2019)" --> Previously not assigned, still" PES (2019)"Copy the code

Example 2:

Input: names = [" gta ", "gta (1)", "gta", "avalon"] output: [" gta ", "gta (1)", "gta (2)", "avalon"] : file system will create the file name like this: "Gta" --> not previously allocated, still "gTA" "GTA (1)" --> Not previously allocated, still" GTA (1)" "gTA" --> Not previously allocated, still "GTA (1)" The actual file created is called "gta(2)". "Avalon" --> Previously unassigned, still "avalon"Copy the code

Example 3:

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"] output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"] Explanation: When the last folder is created, the minimum positive valid k is 4 and the file name becomes "onepiece(4)".Copy the code

Example 4:

Input: names = [" wano ", "wano", "wano", "wano"] output: [" wano ", "wano (1)", "wano (2)", "wano (3)"] explanation: Each time you create the folder "wano", simply increment the value of k in the suffix.Copy the code

Example 5:

Input: names = [kaido ", "" kaido (1)", "kaido", "kaido (1)"] output: [" kaido ", "kaido (1)", "kaido (2)", "kaido (1) (1)"] explanation: Note that if a filename with a suffix is occupied, a new suffix (k) is added to the name as usual.Copy the code

 

Tip:

  • 1 <= names.length <= 5 * 10^4
  • 1 <= names[i].length <= 20
  • names[i]Consists of lowercase letters, numbers, and/or parentheses.

Train of thought

  • This problem is easy to fall into a mistake, that is, I have to unwrap the following several brackets, and then extract the numbers inside a sum. We don’t really care what the numbers are in parentheses;

  • We just need to use a set object to record whether the current file name has been present before. If so, we add it to the file name accumulation method. If not, we record its existence.

  • If (count++) does exist, if (count++) does not exist, modify it directly. The value of count starts at 1, and then we iterate to see if it already exists.

  • That way we can implement our result through a loop, and of course, the worst case is that we’re counting each time we count, so the worst case in terms of complexity is going through the nested array O(n ^ 2) twice.

implementation

/ * * *@param {string[]} names
 * @return {string[]}* /
var getFolderNames = function(names) {
    // Records whether the current object appears
    let set = new Set(a);// add the suffix to the function
    function handleAddNumber(index, count = 1) {
        // The current index already has a value, so increment
        while (set.has(`${names[index]}(${count}) `)) {
            count++;
        }

        names[index] = `${names[index]}(${count}) `;
        set.add(names[index]);
    }

    for (let i = 0; i < names.length; i++) {
        // Check if this element is present, if so, put it in increment
        if (set.has(names[i])) {
            handleAddNumber(i);
        } else {
            // If not, record itset.add(names[i]); }}return names;
};
Copy the code

To optimize the

  • We can change the set method to map, and then record the number of digits of each element. In this way, we can save a searching process.

  • But not at all? Well, it’s not, because when we’re done, we suddenly insert an element into the original position, and we don’t know that unless we cut off the last parenthesis to add the prefix, which obviously makes the code look more cumbersome;

  • So we will still check, but we will record each time before the check, to save us the part of time to repeat the operation.

The final code

/ * * *@param {string[]} names
 * @return {string[]}* /
var getFolderNames = function(names) {
    // Records the last index of the current object
    let map = new Map(a);for (let i = 0; i < names.length; i++) {
        // Check if this element is present, if so, put it in increment
        if (map.has(names[i])) {
            let count = map.get(names[i]) + 1;

            while (map.has(names[i] + ` (${count}) `)) {
                count++;
            }
            
            map.set(names[i], count);
            names[i] += ` (${count}) `;
        }
           
        // Record the current element
        map.set(names[i], 0);
    }

    return names;
};
Copy the code

The final result

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.