425. Word Squares
LeetCode
hard
оригинал: C#
#array
#backtracking
#csharp
#hard
#hash-table
#leetcode
#prefix-sum
#search
#string
#tree
Дан массив уникальных строк 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# решение
сопоставлено/оригинал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++ решение
auto-draft, проверить перед отправкой#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 решение
сопоставлено/оригинал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 решение
сопоставлено/оригинал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] || [];
}
}Algorithm
Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов.
При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов.
Используйте алгоритм с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, вернитесь к предыдущему состоянию и попробуйте другое слово.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.