Задача: 965. Univalued Binary Tree
Сложность: medium

Дан список слов, и нам нужно реализовать проверку орфографии, которая преобразует слово запроса в правильное слово.

Для данного слова запроса, проверка орфографии обрабатывает две категории ошибок правописания:
Заглавные буквы: если запрос совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и в списке слов.
Пример: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
Пример: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
Пример: wordlist = ["yellow"], query = "yellow": correct = "yellow"

Ошибки гласных: если после замены гласных ('a', 'e', 'i', 'o', 'u') в слове запроса на любую гласную по отдельности оно совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и совпадающее слово в списке слов.
Пример: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
Пример: wordlist = ["YellOw"], query = "yeellow": correct = "" (нет совпадения)
Пример: wordlist = ["YellOw"], query = "yllw": correct = "" (нет совпадения)

Кроме того, проверка орфографии работает по следующим правилам приоритета:
Когда запрос точно совпадает со словом в списке слов (с учетом регистра), вы должны вернуть это же слово.
Когда запрос совпадает со словом за исключением регистра, вы должны вернуть первое такое совпадение в списке слов.
Когда запрос совпадает со словом за исключением ошибок гласных, вы должны вернуть первое такое совпадение в списке слов.
Если запрос не имеет совпадений в списке слов, вы должны вернуть пустую строку.
Дан массив запросов, верните список слов answer, где answer[i] — правильное слово для query = queries[i].

Пример:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

👨‍💻 Алгоритм:

1⃣Используйте множество для хранения слов из списка, чтобы проверять точные совпадения.

2⃣Используйте хэш-таблицу для хранения слов в нижнем регистре и соответствующих слов из списка для проверки совпадений без учета регистра.

3⃣Используйте хэш-таблицу для хранения слов в нижнем регистре с замененными гласными символами и соответствующих слов из списка для проверки совпадений с ошибками гласных.

😎 Решение:

class Solution {
    private $wordsPerfect;
    private $wordsCap;
    private $wordsVow;

    /**
     * @param String[] $wordlist
     * @param String[] $queries
     * @return String[]
     */
    function spellchecker($wordlist, $queries) {
        $this->wordsPerfect = array_flip($wordlist);
        $this->wordsCap = [];
        $this->wordsVow = [];

        foreach ($wordlist as $word) {
            $wordlow = strtolower($word);
            if (!isset($this->wordsCap[$wordlow])) {
                $this->wordsCap[$wordlow] = $word;
            }

            $wordlowDV = $this->devowel($wordlow);
            if (!isset($this->wordsVow[$wordlowDV])) {
                $this->wordsVow[$wordlowDV] = $word;
            }
        }

        $result = [];
        foreach ($queries as $query) {
            $result[] = $this->solve($query);
        }
        return $result;
    }

    private function solve($query) {
        if (isset($this->wordsPerfect[$query])) {
            return $query;
        }

        $queryL = strtolower($query);
        if (isset($this->wordsCap[$queryL])) {
            return $this->wordsCap[$queryL];
        }

        $queryLV = $this->devowel($queryL);
        if (isset($this->wordsVow[$queryLV])) {
            return $this->wordsVow[$queryLV];
        }

        return "";
    }

    private function devowel($word) {
        return preg_replace('/[aeiou]/', '*', $word);
    }
}

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