Word Squares - Leetcode Solution

The Word Squares problem on Leetcode requires building a word square with a given set of words. First, let's understand what a word square is.

A Word Square is a set of words arranged in a square such that the words in each row and column are the same. For instance, the set of words ["area", "roam", "emit", "mire"] can be arranged into a word square of the following form:

a r e a
r o a m
e m i t
a m i r

In this particular example, the first row and first column have the same word "area", the second row and second column have the word "roam", and so on.

To solve this problem, we need to come up with a recursive solution that builds a word square one row at a time. The first step is to build the first row of the word square by taking each word one at a time and then recursively building the remaining rows.

The recursive function takes in the current state of the word square and an index indicating which word to use for the current row.

def build_word_squares(words):
    n = len(words[0])
    results = []
    word_map = build_word_map(words)
    build_word_square([], 0, n, word_map, results)
    return results

The words argument is a list of words to build the word square from, n is the length of each word, results is a list to hold all the valid word squares that are built, and word_map is a dictionary containing the words grouped by their prefixes. We'll come back to word_map later.

The build_word_square function is the recursive function that builds a word square row by row. Let's take a closer look at how it works.

def build_word_square(square, row, n, word_map, results):
    if row == n:
        results.append(square)
        return
    
    prefix = ''.join(square[j][row] for j in range(row))

    if prefix in word_map:
        for word in word_map[prefix]:
            build_word_square(square + [word], row + 1, n, word_map, results)

The function takes in square which is the current state of the word square, row which is the current row we are building, word_map which is the dictionary of words grouped by prefixes, and results, which is the list to hold all the valid word squares that are built.

The base case is when we have completed building the word square, i.e., when row is equal to n. At this point, we append the square to results and return.

Next, we compute the prefix for the current row. The prefix is a string consisting of the first row letters of each word in the current square. This is used to check if there are any words that start with this prefix.

We check if the prefix exists in the word_map. If it does, we iterate over all the words in the word_map that start with this prefix, and recursively call build_word_square with the new square which includes the current word, row incremented by 1, and the other arguments.

Let's implement the build_word_map function, which builds a dictionary mapping prefixes to a list of words that start with that prefix.

def build_word_map(words):
    word_map = defaultdict(list)
    for word in words:
        for i in range(len(word)):
            word_map[word[:i+1]].append(word)
    return word_map

The build_word_map function takes in the list of words and returns a dictionary where the keys are the prefixes of the words in the list, and the values are lists of words that start with that prefix.

Finally, we can put everything together and test the solution with a sample input.

words = ["area", "roam", "emit", "mire"]
print(build_word_squares(words))
# Output: [['aera', 'roam', 'emit', 'mire'], ['area', 'roam', 'emit', 'amir']]

The output is a list of all the valid word squares that can be built with the given words.

1