Сложность: hard
Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.
Пример:
Input: letters = ["c","f","j"], target = "a"
Output: "c"
👨💻 Алгоритм:
1⃣Сохраните слова и их индексы в словаре.
2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.
3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.
😎 Решение:
class WordFilter(words: Array<String>) {
private val prefixSuffixMap = mutableMapOf<String, Int>()
init {
for ((index, word) in words.withIndex()) {
val length = word.length
for (prefixLength in 1..length) {
for (suffixLength in 1..length) {
val prefix = word.substring(0, prefixLength)
val suffix = word.substring(length - suffixLength)
val key = "$prefix#$suffix"
prefixSuffixMap[key] = index
}
}
}
}
fun f(pref: String, suff: String): Int {
val key = "$pref#$suff"
return prefixSuffixMap[key] ?: -1
}
}Ставь 👍 и забирай 📚 Базу знаний