
Problem Statement
In this problem, we are given an array of unique strings named words
. Our goal is to construct all possible word squares using these strings. A word from the array can be repeatedly used in different word squares. The result can be presented in any order without affecting correctness.
A word square is a sequence of strings that form a square matrix where the strings must read the same horizontally (left to right) and vertically (top to bottom) along the kth row and column for all possible k, where 0 <= k < max(numRows, numColumns)
.
For clarity, consider the word sequence ["ball","area","lead","lady"]
. This set of words forms an appropriate word square because each word can be read identically across and down, making squares of words align perfectly both horizontally and vertically.
Examples
Example 1
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).
Example 2
Input:
words = ["abat","baba","atan","atal"]
Output:
[["baba","abat","baba","atal"],["baba","abat","baba","atan"]]
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).
Constraints
1 <= words.length <= 1000
1 <= words[i].length <= 4
- All
words[i]
have the same length. words[i]
consists of only lowercase English letters.- All
words[i]
are unique.
Approach and Intuition
To approach this problem, let's break down the conditions and understand the concept through the examples provided:
Example Understanding
Example 1:
The input list is["area","lead","wall","lady","ball"]
. Two word squares possible here are:[["ball","area","lead","lady"],["wall","area","lead","lady"]]
Analyzing one square:
ball area lead lady
Here,
b
,a
,l
,l
forms both the first column and the first row, and so on for other rows and columns.Example 2:
Given["abat","baba","atan","atal"]
, we can generate:[["baba","abat","baba","atal"],["baba","abat","baba","atan"]]
One such square would be:
baba abat baba atal
Notice how each row mirrors its respective column.
Key Observations and Steps:
- The characters at each position across the words must lead to a valid mirror horizontally and vertically upon placement.
- Given that all words are of the same length and are unique, but can be reused, it's ideal to use a backtracking approach:
- Start forming the word square row by row using the words.
- For each word added to the square, ensure it is consistent with previously added words in forming a valid square as per the kth row and column.
- Continue exploring possible words that can complete the word square, reverting (backtracking) if a word doesn't lead to a valid solution.
- Efficiency can be potentially improved using prefix hashing (storing words by their prefix for quick lookup), especially given the constraints where word length can go up to 4, making this manageable.
This backtracking method, augmented with effective checks for forming valid word squares, ensures that all combinations are explored without redundant calculation, adhering to the unique constraint induced by the problem definition.
Solutions
- Java
class TrieNode {
HashMap<Character, TrieNode> descendants = new HashMap<>();
List<Integer> indices = new ArrayList<>();
public TrieNode() {}
}
class Solution {
int wordLength = 0;
String[] wordArray = null;
TrieNode root = null;
public List<List<String>> wordSquares(String[] words) {
this.wordArray = words;
this.wordLength = words[0].length();
List<List<String>> allResults = new ArrayList<>();
this.constructTrie(words);
for (String word : words) {
LinkedList<String> currentSquare = new LinkedList<>();
currentSquare.addLast(word);
this.depthFirstSearch(1, currentSquare, allResults);
}
return allResults;
}
protected void depthFirstSearch(int depth, LinkedList<String> currentSquare,
List<List<String>> allResults) {
if (depth == wordLength) {
allResults.add(new ArrayList<>(currentSquare));
return;
}
StringBuilder prefixBuilder = new StringBuilder();
for (String word : currentSquare) {
prefixBuilder.append(word.charAt(depth));
}
for (Integer index : this.findWordsByPrefix(prefixBuilder.toString())) {
currentSquare.addLast(this.wordArray[index]);
this.depthFirstSearch(depth + 1, currentSquare, allResults);
currentSquare.removeLast();
}
}
protected void constructTrie(String[] words) {
this.root = new TrieNode();
for (int index = 0; index < words.length; ++index) {
String word = words[index];
TrieNode node = this.root;
for (char character : word.toCharArray()) {
if (!node.descendants.containsKey(character)) {
TrieNode newNode = new TrieNode();
node.descendants.put(character, newNode);
}
node = node.descendants.get(character);
node.indices.add(index);
}
}
}
protected List<Integer> findWordsByPrefix(String prefix) {
TrieNode node = this.root;
for (char character : prefix.toCharArray()) {
if (node.descendants.containsKey(character)) {
node = node.descendants.get(character);
} else {
return new ArrayList<>();
}
}
return node.indices;
}
}
The Word Squares solution in Java utilizes a combination of Trie data structure and depth-first search (DFS) to efficiently generate all possible word squares given a list of words. Here’s a breakdown of the essential steps and components involved in the solution:
TrieNode Class: Represents each node in the Trie. Each node stores its descendants (as a hashmap where the key is the character and the value is the next TrieNode) and indices (a list that represents indices in the array of words where words starting with this Trie prefix can be found).
Solution Class: Contains the main logic for generating word squares:
Variables:
wordLength
stores the length of the words.wordArray
is an array of the input words.root
is the Trie root node.
wordSquares Method: This is the entry method that initializes other methods and variables to set up the Trie and start the recursion:
- Initializes the
wordArray
andwordLength
based on input. - Constructs a Trie from the words for fast prefix lookup.
- Iterates over the array of words to initialize DFS for forming the word squares.
- Initializes the
depthFirstSearch Method: Handles the recursive generation of word squares:
- Base case: If the depth equals
wordLength
, adds the current square to the result set. - Constructs the prefix for the next potential word using the current depth.
- Looks up potential words using the Trie and continues depth-first search recursively.
- Base case: If the depth equals
constructTrie Method: Builds the Trie from the given array of words:
- Iterates through each word and character to construct the Trie.
- Updates descendant nodes and indices list as it progresses.
findWordsByPrefix Method: Retrieves a list of indices pointing to words that start with the specified prefix using the Trie structure:
- Navigates through the Trie according to each character in the prefix.
- If the prefix fully exists, returns the list of indices at the end of the prefix path.
This Java class meticulously assembles word squares by using the Trie to manage prefixes for building squares row by row, and DFS to explore all potential word combinations based on the prefixes. The efficient lookup operations enabled by Trie and optimized recursion make this solution effective for solving the Word Squares problem.
No comments yet.