LeetCode 425: Word Squares Solution
Master LeetCode problem 425 (Word Squares), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
425. Word Squares
Problem Explanation
Explanation:
The problem asks us to find all word squares from a given list of words. A word square is a crossword puzzle where the words in each row and column are the same.
To solve this problem, we can use a backtracking approach. We start by constructing a trie data structure to store all the words. We then iterate through each word in the list and recursively build the word square by trying out all possible prefixes that match the next row's words.
Here are the detailed steps:
- Build a trie data structure from the given list of words.
- Initialize an empty list to store the current word square being constructed.
- Start the backtracking process by iterating through each word in the list.
- For each word, add it to the current word square and recursively try to find the next word that matches the columns of the current square.
- If a valid word square is found, add it to the result list.
- Backtrack by removing the last word added to the current word square and continue the search.
Time Complexity:
- Building the trie: O(N * L), where N is the number of words and L is the average length of the words.
- Backtracking: O(N * 26^L), where N is the number of words and L is the length of each word. The worst-case scenario is trying all possible prefixes for each word.
- Overall time complexity: O(N * L + N * 26^L)
Space Complexity:
- Trie data structure: O(N * L)
- Recursive call stack: O(L)
- Overall space complexity: O(N * L)
: :
Solution Code
class Solution {
class TrieNode {
TrieNode[] children;
List<String> startsWith;
TrieNode() {
children = new TrieNode[26];
startsWith = new ArrayList<>();
}
}
private TrieNode root = new TrieNode();
private void buildTrie(String[] words) {
for (String word : words) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node.startsWith.add(word);
node = node.children[index];
}
}
}
private List<String> findByPrefix(String prefix) {
TrieNode node = root;
for (char ch : prefix.toCharArray()) {
int index = ch - 'a';
if (node.children[index] == null) {
return new ArrayList<>();
}
node = node.children[index];
}
return node.startsWith;
}
private void backtrack(List<List<String>> squares, List<String> square, int index, int n) {
if (index == n) {
squares.add(new ArrayList<>(square));
return;
}
String prefix = "";
for (int i = 0; i < index; i++) {
prefix += square.get(i).charAt(index);
}
List<String> candidates = findByPrefix(prefix);
for (String candidate : candidates) {
square.add(candidate);
backtrack(squares, square, index + 1, n);
square.remove(square.size() - 1);
}
}
public List<List<String>> wordSquares(String[] words) {
buildTrie(words);
List<List<String>> squares = new ArrayList<>();
List<String> square = new ArrayList<>();
int n = words[0].length();
for (String word : words) {
square.add(word);
backtrack(squares, square, 1, n);
square.remove(square.size() - 1);
}
return squares;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 425 (Word Squares)?
This page provides optimized solutions for LeetCode problem 425 (Word Squares) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 425 (Word Squares)?
The time complexity for LeetCode 425 (Word Squares) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 425 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 425 in Java, C++, or Python.