425. Word Squares
LeetCode
hard
original: C#
#array
#backtracking
#csharp
#hard
#hash-table
#leetcode
#prefix-sum
#search
#string
#tree
Task text is translated from Russian for the selected interface language. Code is left unchanged.
Дан array уникальных строк words, return все квадраты слов, которые можно построить из этих слов. Одно и то же слово из words можно использовать несколько раз. Вы можете вернуть ответ в любом порядке.
Последовательность строк образует допустимый квадрат слов, если k-я string и k-й столбец читаются одинаково, где 0 <= k < max(количество строк, количество столбцов).
НаExample, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали.
Example:
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/originalusing 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/originalclass 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/originalclass 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] || [];
}
}Algorithm
Постройте хеш-таблицу из Inputных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов.
При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов.
Используйте Algorithm с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, returnсь к предыдущему состоянию и попробуйте другое слово.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.
There are no active vacancies yet.