Задача: 745. Prefix and Suffix Search
Сложность: 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 {
    private $prefixSuffixMap = [];
    
    function __construct($words) {
        foreach ($words as $index => $word) {
            $length = strlen($word);
            for ($prefixLength = 1; $prefixLength <= $length; $prefixLength++) {
                for ($suffixLength = 1; $suffixLength <= $length; $suffixLength++) {
                    $prefix = substr($word, 0, $prefixLength);
                    $suffix = substr($word, $length - $suffixLength);
                    $key = $prefix . '#' . $suffix;
                    $this->prefixSuffixMap[$key] = $index;
                }
            }
        }
    }
    
    function f($pref, $suff) {
        $key = $pref . '#' . $suff;
        return array_key_exists($key, $this->prefixSuffixMap) ? $this->prefixSuffixMap[$key] : -1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний