Задача: 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 {
    int N = 0;
    String[] words = null;
    HashMap<String, List<String>> prefixHashTable = null;

    public List<List<String>> wordSquares(String[] words) {
        this.words = words;
        this.N = words[0].length();

        List<List<String>> results = new ArrayList<>();
        this.buildPrefixHashTable(words);

        for (String word : words) {
            LinkedList<String> wordSquares = new LinkedList<>();
            wordSquares.addLast(word);
            this.backtracking(1, wordSquares, results);
        }
        return results;
    }

    protected void backtracking(int step, LinkedList<String> wordSquares, List<List<String>> results) {
        if (step == N) {
            results.add(new ArrayList<>(wordSquares));
            return;
        }

        StringBuilder prefix = new StringBuilder();
        for (String word : wordSquares) {
            prefix.append(word.charAt(step));
        }

        for (String candidate : this.getWordsWithPrefix(prefix.toString())) {
            wordSquares.addLast(candidate);
            this.backtracking(step + 1, wordSquares, results);
            wordSquares.removeLast();
        }
    }

    protected void buildPrefixHashTable(String[] words) {
        this.prefixHashTable = new HashMap<>();

        for (String word : words) {
            for (int i = 1; i < this.N; ++i) {
                String prefix = word.substring(0, i);
                List<String> wordList = this.prefixHashTable.get(prefix);
                if (wordList == null) {
                    wordList = new ArrayList<>();
                    wordList.add(word);
                    this.prefixHashTable.put(prefix, wordList);
                } else {
                    wordList.add(word);
                }
            }
        }
    }

    protected List<String> getWordsWithPrefix(String prefix) {
        List<String> wordList = this.prefixHashTable.get(prefix);
        return (wordList != null ? wordList : new ArrayList<>());
    }
}

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