Сложность: 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 {
constructor(words) {
this.prefixSuffixMap = new Map();
for (let index = 0; index < words.length; index++) {
const word = words[index];
const length = word.length;
for (let prefixLength = 1; prefixLength <= length; prefixLength++) {
for (let suffixLength = 1; suffixLength <= length; suffixLength++) {
const prefix = word.substring(0, prefixLength);
const suffix = word.substring(length - suffixLength);
const key = prefix + '#' + suffix;
this.prefixSuffixMap.set(key, index);
}
}
}
}
f(pref, suff) {
const key = pref + '#' + suff;
return this.prefixSuffixMap.has(key) ? this.prefixSuffixMap.get(key) : -1;
}
}Ставь 👍 и забирай 📚 Базу знаний