В файловой системе Windows две папки/файла не могут иметь одинаковые имена. Если вы введете имя папки, которое использовалось ранее, система добавит к его имени суффикс в виде (k), где k — наименьшее положительное целое число, при котором полученное имя остается уникальным.
Постановка задачи
Дан массив строк d irNames размера n. Вы создадите n папок в вашей файловой системе Windows, так что на i-й минуте вы создадите папку с именем dirNames[i]. Задача состоит в том, чтобы вернуть массив строк длины n, где ans[i] — фактическое имя, которое система присвоит i-й папке при ее создании.
Примеры:
Input: dirNames = ["abc","pqrs","mnp","abc(2019)"] Output: ["abc","pqrs","mnp","abc(2019)"]
Объяснение: Давайте посмотрим, как файловая система создает имена папок:
«abc» -> ранее не назначалось, остается «abc»
«pqrs» -> не назначалось ранее, остается «pqrs»
«mnp» -> не назначалось ранее, остается «mnp »
abc(2019)» -> ранее не назначалось, остается «abc(2019)»
Input: dirNames = ["cod","cod(1)","cod","test"] Output: ["cod","cod(1)","cod(2)","test"]
Объяснение: Давайте посмотрим, как файловая система создает имена папок:
«cod» -> ранее не назначалось, остается «cod»
«cod(1)» -> не назначалось ранее, остается «cod(1)»
«cod» -> имя зарезервировано, система добавляет (k), так как «cod(1)» также зарезервировано, системы ставят k = 2. становится «cod(2)»
«test» -> ранее не назначалось, остается «test»
Решение
Мы будем поддерживать карту для хранения того, сколько раз уже встречается конкретное имя. Затем итеративно проверьте, пришло ли имя уже и содержит ли оно номер в скобках. Затем увеличивайте число до тех пор, пока этого не будет. А пока обновите и карту.
import
java.io.*;
import
java.util.*;
public
class
GFG {
// Main Method
public
static
void
main(String[] args)
throws
IOException
{
String[] dirNames
= {
"cod"
,
"cod(1)"
,
"cod"
,
"test"
};
String[] output = getFolderNames(dirNames);
for
(String i : output) {
System.out.print(i +
" "
);
}
}
public
static
String[] getFolderNames(String[] names)
{
Map<String, Integer> m =
new
HashMap<>();
for
(
int
i =
; i < names.length;
m.put(names[i],
1
), i++)
if
(m.containsKey(names[i])) {
int
k = m.get(names[i]);
while
(
m.containsKey(names[i] +
"("
+ k +
")"
))
k++;
m.put(names[i], k +
1
);
names[i] = names[i] +
"("
+ k +
")"
;
}
return
names;
}
}
Выход:
cod cod(1) cod(2) test
- Временная сложность: O(n)
- Космическая сложность: O(n 2)