Сложность: hard
Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):
"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.
Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.
Пример:
Input: target = "apple", dictionary = ["blade"]
Output: "a4"
👨💻 Алгоритм:
1⃣Создайте множество всех аббревиатур из словаря, вычислив их все возможные аббревиатуры.
2⃣Сгенерируйте все возможные аббревиатуры для строки target.
3⃣Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.
😎 Решение:
func generateAbbreviations(_ word: String) -> Set<String> {
var result = Set<String>()
generateAbbreviationsHelper(Array(word), "", 0, 0, &result)
return result
}
func generateAbbreviationsHelper(_ word: [Character], _ current: String, _ pos: Int, _ count: Int, _ result: inout Set<String>) {
if pos == word.count {
result.insert(current + (count > 0 ? String(count) : ""))
return
}
generateAbbreviationsHelper(word, current, pos + 1, count + 1, &result)
generateAbbreviationsHelper(word, current + (count > 0 ? String(count) : "") + String(word[pos]), pos + 1, 0, &result)
}
func minAbbreviation(_ target: String, _ dictionary: [String]) -> String {
let targetAbbrs = generateAbbreviations(target)
var dictAbbrs = Set<String>()
for word in dictionary {
dictAbbrs.formUnion(generateAbbreviations(word))
}
let validAbbrs = targetAbbrs.subtracting(dictAbbrs)
return validAbbrs.sorted(by: { $0.count < $1.count }).first!
}Ставь 👍 и забирай 📚 Базу знаний