425. Word Squares

Problem Description

The LeetCode problem asks for all possible word squares that can be formed from a given list of unique words. A word square is a special type of square grid of letters where every row and every column forms an identical word. This means that if you read the letters horizontally or vertically, the words should be the same. The sequence must satisfy the condition that the kth row's kth letter is the same as the kth column's kth letter, for every k from 0 up to the size of the largest row or column.

A crucial detail is that the same word can be used multiple times in building word squares, which greatly increases the number of potential combinations.

For example, with the words ["ball","area","lead","lady"], the following word square can be formed:

1ball
2area
3lead
4lady

Each row and column form the same words in this example. We are tasked with finding and returning all possible such squares that can be assembled given the input array of words.

Intuition

The intuition behind the solution involves several steps:

1. Prefix Matching: A vital insight is that while building a word square, when we append a word, it determines the prefix that the next word must match. The progression is therefore by matching prefixes, word by word.

2. Backtracking: An algorithmic technique that incrementally builds candidates to the solutions and abandons a candidate as soon as it determines this candidate cannot possibly lead to a valid word square.

3. Trie Data Structure: This is a specialized tree-like data structure that's used for prefix matching. Each node stores links to other nodes - one for each possible alphabetic value. This structure efficiently retrieves all words that have a common prefix.

In the provided solution, we are using a Trie to store the words with a slight modification. Each Trie node keeps an array of indices, which is a list of all word indices from the original list that contain the prefix represented by the path from the root to that node.

Here's how we arrive at the solution:

1. Building the Trie: We create a Trie and insert each word, keeping track of their indices within the original list.

2. Searching the Trie: For building a word square, we start with the first word. For the next word to form a valid square, its prefix should match the second letter of the first word and so on. We use the Trie to look up all words with this prefix.

3. Recursive Exploration with Backtracking: Next, we try to recursively add each of these words to the current word square in construction and check the next prefix that must be matched. If at any point, no words match the required prefix, we back out of the last step (we "backtrack") and try a different word. This process continues until:

   • We build a complete word square of the same size as the length of any word in the input list.
   • We exhaust all possibilities.

This solution method is efficient as it cuts down on the search space using the Trie structure for prefix look-ups and backtracking to avoid unnecessary exploration.

Learn more about Trie and Backtracking patterns.

Solution Approach

The solution involves implementing a backtracking algorithm utilizing a Trie data structure to efficiently search for words that can form word squares. Let's walk through the implementation step by step:

1. Trie Construction:

   • We define a Trie class with an initialization (__init__) method that creates 26 children (one for each letter of the alphabet) and an empty list v for keeping track of word indices.
   • The insert method adds a word to the Trie, character by character. For each character, we find the right child node to move to, or create a new Trie node if it does not exist. After reaching the end of a word, we append the word's index to the node's v list, capturing all indices where the path through the Trie matches the inserted word.
   • The search method follows the Trie nodes according to the characters of the given prefix, returning the list of word indices that contain the prefix if it exists, or an empty list otherwise.

2. Backtracking with Trie:

   • In the wordSquares function of the Solution class, we first build a Trie from our words list, using the insert method for each word accompanied by its index.
   • We define an inner function dfs(t) for backtracking and building the word squares:
     • It takes the current partial word square t as an argument.
     • If t contains enough words to form a square (the length of t equals the length of a word), we add it to ans, our solution list.
     • Otherwise, for finding the next word, we look at the idxth characters of the words in t to form the next prefix we want to match.
     • We retrieve all indices of words with that prefix using the search method of the Trie.
     • We loop through these indices, adding each corresponding word to t and calling dfs(t) recursively before popping the word off t.
   • Finally, we start our search by iterating over each word in words and initiating a recursion with a word square starting with that word. The initial list [w] is passed to dfs to begin building the square.

The dfs function systematically constructs potential word squares, and the Trie enables fast lookups for words that can extend the partial squares by matching the required prefixes.

The wordSquares function ultimately returns ans, the collected list of all valid word squares, after exploring all possible combinations through recursive backtracking with the help of the Trie.

Example Walkthrough

Let's consider a smaller list of words to illustrate the solution approach: ["ab", "bc"]. The goal is to find all word squares that can be formed with these words. Here's how we would walk through the given solution approach:

1. Trie Construction:

   • We create a Trie and insert each of the words with their indices. Our Trie will look like this after insertion:

     • Root
       • a (children: b - index [0])
       • b (children: c - index [1])

   • The Trie stores the index of "ab" under the branch 'a' -> 'b', and the index of "bc" under the branch 'b' -> 'c'.

2. Backtracking with Trie:

   • We initialize ans as an empty list to collect valid word squares.
   • Starting with the word "ab", we consider this as the first word in our potential word square. This word determines that the second word in the square must start with 'b' because 'b' is the second character in "ab".
   • We then use the Trie to search for words beginning with 'b'. The Trie yields "bc", which matches the requirement.
   • We then form a partial word square ["ab", "bc"]. Since the number of words (2) is equal to the length of the words "ab" and "bc", we've successfully formed a valid word square and we add this to the ans list.

No other word squares can be formed using "ab" as the starting word. We would then repeat the process for "bc" as the starting word:

1. Start with "bc" as the first word of the square.
2. The second word must start with 'c'. However, our list does not have a word that starts with 'c', so no further word squares can be formed in this case.

The ans list now contains the single valid word square ["ab", "bc"]. We return this as the final result.

The example has been kept deliberately simple due to the limited number of words. In a scenario with a more extensive list of words, the Trie and backtracking process would be used more exhaustively to form all possible word squares.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the wordSquares method primarily depends on the number of words n, the length of each word l, and the branching factor at each node of the Trie (which is at most 26, the number of lowercase English letters).

First, constructing the Trie takes O(n*l), because we traverse each word of length l and insert it into the Trie.

For each word, we start a depth-first search (DFS):

• In the worst case, there can be n choices for the first word, n for the second, and so on, making it O(n^l) without optimization.
• The Trie lookup reduces the branching factor significantly. For each node during DFS, instead of trying n possibilities, we look at the children that match the prefix formed by the current word square, which is an O(l) operation since at each recursive level we collect at most l indexes represented by the value list v.
• The depth of the DFS is equal to the length of the words l, since we're forming squares, meaning we stop when the number of words equals the length of the words.

Assuming k is the average number of indexes stored in the Trie node's value list v after searching with prefixes, the approximate time complexity becomes O(n * k^(l-1) * l). This is because we perform the Trie search for every prefix formed in the recursion after the first word is chosen, and each search costs O(l) (since we're constructing the prefix from the partial word square and then iterating through the v list of the Trie node).

Space Complexity

The space complexity of the code is dictated by:

• The Trie storage, which takes O(26*m*l), where m is the average length of each word when considering all nodes (with a maximum of 26 since each node has up to 26 children).
• The recursion call stack, which will grow to a depth of l, along with the temporary array t in each recursive call and the pref constructed at each node, totaling O(l^2).
• The solution array ans, which stores completed word squares. The total number of squares cannot exceed n^l, and each square has l words of length l, making it O(n^l * l^2).

Since the space taken by the solution ans will outweigh the others for large inputs, the dominating term in the space complexity is O(n^l * l^2), representing the output space.

Combining these, the overall space complexity is O(26 * m * l + l^2 + n^l * l^2). Simplifying, since 26 and m are constants and less significant than n^l, we get O(n^l * l^2).

Learn more about how to find time and space complexity quickly using problem constraints.