← Static tasks

425. Word Squares

leetcode hard

#array#backtracking#csharp#hard#hash-table#leetcode#prefix-sum#search#string#tree

Task

Дан массив уникальных строк 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).

C# solution

matched/original
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
    private int N = 0;
    private string[] words = null;
    private Dictionary<string, List<string>> prefixHashTable = null;
    public IList<IList<string>> WordSquares(string[] words) {
        this.words = words;
        this.N = words[0].Length;
        List<IList<string>> results = new List<IList<string>>();
        this.BuildPrefixHashTable(words);
        foreach (string word in words) {
            LinkedList<string> wordSquares = new LinkedList<string>();
            wordSquares.AddLast(word);
            this.Backtracking(1, wordSquares, results);
        }
        return results;
    }
    protected void Backtracking(int step, LinkedList<string> wordSquares, List<IList<string>> results) {
        if (step == N) {
            results.Add(new List<string>(wordSquares));
            return;
        }
        StringBuilder prefix = new StringBuilder();
        foreach (string word in wordSquares) {
            prefix.Append(word[step]);
        }
        foreach (string candidate in this.GetWordsWithPrefix(prefix.ToString())) {
           wordSquares.AddLast(candidate);
            this.Backtracking(step + 1, wordSquares, results);
            wordSquares.RemoveLast();
        }
    }
    protected void BuildPrefixHashTable(string[] words) {
        this.prefixHashTable = new Dictionary<string, List<string>>();
        foreach (string word in words) {
            for (int i = 1; i < this.N; ++i) {
                string prefix = word.Substring(0, i);
                if (!this.prefixHashTable.ContainsKey(prefix)) {
                    this.prefixHashTable[prefix] = new List<string>();
                }
                this.prefixHashTable[prefix].Add(word);
            }
        }
    }
    protected IList<string> GetWordsWithPrefix(string prefix) {
        if (this.prefixHashTable.ContainsKey(prefix)) {
            return this.prefixHashTable[prefix];
        }
        return new List<string>();
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int N = 0;
    private vector<string> words = null;
    private unordered_map<string, List<string>> prefixHashTable = null;
    public IList<vector<string>> WordSquares(vector<string> words) {
        this.words = words;
        this.N = words[0].size();
        List<vector<string>> results = new List<vector<string>>();
        this.BuildPrefixHashTable(words);
        foreach (string word in words) {
            LinkedList<string> wordSquares = new LinkedList<string>();
            wordSquares.AddLast(word);
            this.Backtracking(1, wordSquares, results);
        }
        return results;
    }
    protected void Backtracking(int step, LinkedList<string> wordSquares, List<vector<string>> results) {
        if (step == N) {
            results.push_back(new List<string>(wordSquares));
            return;
        }
        StringBuilder prefix = new StringBuilder();
        foreach (string word in wordSquares) {
            prefix.Append(word[step]);
        }
        foreach (string candidate in this.GetWordsWithPrefix(prefix.ToString())) {
           wordSquares.AddLast(candidate);
            this.Backtracking(step + 1, wordSquares, results);
            wordSquares.RemoveLast();
        }
    }
    protected void BuildPrefixHashTable(vector<string> words) {
        this.prefixHashTable = new unordered_map<string, List<string>>();
        foreach (string word in words) {
            for (int i = 1; i < this.N; ++i) {
                string prefix = word.Substring(0, i);
                if (!this.prefixHashTable.count(prefix)) {
                    this.prefixHashTable[prefix] = new List<string>();
                }
                this.prefixHashTable[prefix].push_back(word);
            }
        }
    }
    protected vector<string> GetWordsWithPrefix(string prefix) {
        if (this.prefixHashTable.count(prefix)) {
            return this.prefixHashTable[prefix];
        }
        return new List<string>();
    }
}

Java solution

matched/original
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<>());
    }
}

JavaScript solution

matched/original
class Solution {
    constructor() {
        this.N = 0;
        this.words = [];
        this.prefixHashTable = {};
    }

    wordSquares(words) {
        this.words = words;
        this.N = words[0].length;

        const results = [];
        this.buildPrefixHashTable(words);

        for (const word of words) {
            const wordSquares = [word];
            this.backtracking(1, wordSquares, results);
        }
        return results;
    }

    backtracking(step, wordSquares, results) {
        if (step === this.N) {
            results.push([...wordSquares]);
            return;
        }

        const prefix = wordSquares.map(word => word[step]).join('');
        for (const candidate of this.getWordsWithPrefix(prefix)) {
            wordSquares.push(candidate);
            this.backtracking(step + 1, wordSquares, results);
            wordSquares.pop();
        }
    }

    buildPrefixHashTable(words) {
        for (const word of words) {
            for (let i = 1; i < this.N; i++) {
                const prefix = word.slice(0, i);
                if (!this.prefixHashTable[prefix]) {
                    this.prefixHashTable[prefix] = [];
                }
                this.prefixHashTable[prefix].push(word);
            }
        }
    }

    getWordsWithPrefix(prefix) {
        return this.prefixHashTable[prefix] || [];
    }
}

Explanation

Algorithm

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

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

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

😎