Задача: 425. Word Squares
Сложность: hard

Дан массив уникальных строк words, верните все квадраты слов, которые можно построить из этих слов. Одно и то же слово из words можно использовать несколько раз. Вы можете вернуть ответ в любом порядке.

Последовательность строк образует допустимый квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(количество строк, количество столбцов).

Например, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали.

Пример:

Input: words = ["area","lead","wall","lady","ball"]
Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

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

1⃣Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов.

2⃣При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов.

3⃣Используйте алгоритм с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, вернитесь к предыдущему состоянию и попробуйте другое слово.

😎 Решение:

class Solution {
    private $N = 0;
    private $words = [];
    private $prefixHashTable = [];

    function wordSquares($words) {
        $this->words = $words;
        $this->N = strlen($words[0]);

        $results = [];
        $this->buildPrefixHashTable($words);

        foreach ($words as $word) {
            $wordSquares = [$word];
            $this->backtracking(1, $wordSquares, $results);
        }
        return $results;
    }

    function backtracking($step, &$wordSquares, &$results) {
        if ($step == $this->N) {
            $results[] = $wordSquares;
            return;
        }

        $prefix = '';
        foreach ($wordSquares as $word) {
            $prefix .= $word[$step];
        }

        foreach ($this->getWordsWithPrefix($prefix) as $candidate) {
            $wordSquares[] = $candidate;
            $this->backtracking($step + 1, $wordSquares, $results);
            array_pop($wordSquares);
        }
    }

    function buildPrefixHashTable($words) {
        foreach ($words as $word) {
            for ($i = 1; $i < $this->N; $i++) {
                $prefix = substr($word, 0, $i);
                if (!isset($this->prefixHashTable[$prefix])) {
                    $this->prefixHashTable[$prefix] = [];
                }
                $this->prefixHashTable[$prefix][] = $word;
            }
        }
    }

    function getWordsWithPrefix($prefix) {
        return isset($this->prefixHashTable[$prefix]) ? $this->prefixHashTable[$prefix] : [];
    }
}

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