Jobs

Interviews

Discussions

Word Squares

Hard

Asked by:

32 views

Topics:

StringsRecursionTrees

Given a list of unique words, return all the possible word squares you can build from them.

A sequence of words forms a valid word square if the k^th row and column read the exact same string, where 0 <= k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically:
```
b a l l
a r e a
l e a d
l a d y
```

Example 1:

Input: words = ["area","ball","dear","lady","lead"]
Output: [["ball","area","lead","lady"],["lady","area","dear","year"]]
Explanation:
The output consists of two word squares. The order of output does not matter.

Example 2:

Input: words = ["abat","baba","atan","atal"]
Output: [["baba","abat","baba","atal"]]
Explanation:
The only word square is the following:
baba
abat
baba
atal

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 5
All words have the same length.
words[i] consists of only lowercase English letters.
All words[i] are unique.

Try coding it in LeetCode

Word Squares

Hard

Asked by:

32 views

Topics:

StringsRecursionTrees

Given a list of unique words, return all the possible word squares you can build from them.

A sequence of words forms a valid word square if the k^th row and column read the exact same string, where 0 <= k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically:
```
b a l l
a r e a
l e a d
l a d y
```

Example 1:

Input: words = ["area","ball","dear","lady","lead"]
Output: [["ball","area","lead","lady"],["lady","area","dear","year"]]
Explanation:
The output consists of two word squares. The order of output does not matter.

Example 2:

Input: words = ["abat","baba","atan","atal"]
Output: [["baba","abat","baba","atal"]]
Explanation:
The only word square is the following:
baba
abat
baba
atal

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 5
All words have the same length.
words[i] consists of only lowercase English letters.
All words[i] are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of a word in the input list, and what is the maximum number of words in the input list?
Can the input list contain empty strings, null values, or words with different lengths?
If multiple word squares are possible, is any valid word square acceptable, or is there a specific ordering or criteria for selecting one?
If no word square is possible given the input, what should the return value be (e.g., an empty list, null)?
Are the words case-sensitive, or should I treat them as case-insensitive?

Brute Force Solution

Approach

The brute force method to form word squares is to try all possible combinations of words. We'll explore every possible arrangement until we find solutions that fit the word square's constraints. Think of it as exhaustively checking every scenario.

Here's how the algorithm would work step-by-step:

Start by picking a word for the first row of the square.
For the second row, try every word from the list. See if the first letter of this word matches the second letter of the first row word.
If it doesn't match, discard this word and try the next one.
If it does match, proceed to select a word for the third row, and check if its first two letters match the third letter of the first row word and the third letter of the second row word, respectively. Repeat this process.
Continue this pattern, row by row, checking if each word aligns correctly with the letters above it.
If at any point the letters don't align, backtrack and try a different word for that row.
When you have formed a complete square where all the letters align correctly both across rows and down columns, you've found a solution. Save that word square.
Repeat this entire process, starting with a different word for the first row, until all possible combinations have been tried.

Code Implementation

def find_word_squares_brute_force(words):
    results = []
    word_length = len(words[0]) if words else 0

    def backtrack(current_square):
        if len(current_square) == word_length:
            results.append(current_square[:])
            return

        # Iterate over all words to find a suitable candidate for the next row
        for word in words:
            if is_valid_word(current_square, word):
                current_square.append(word)
                backtrack(current_square)
                current_square.pop()

    def is_valid_word(current_square, word):
        row_index = len(current_square)

        # Ensures the new word aligns vertically with existing words
        for column_index in range(row_index):
            if current_square[column_index][row_index] != word[column_index]:
                return False
        return True

    # Start the search with each word as the first row
    for word in words:
        backtrack([word])

    return results

Big(O) Analysis

Time Complexity

O(n^(l*l)) – The brute force approach explores all possible combinations of words to form a word square of length l. In the worst-case scenario, for each of the l rows, we might need to consider all n words from the input list. This leads to a nested loop structure where we're essentially trying all possible combinations of words for each position in the square. Therefore, the time complexity is approximately n multiplied by itself l*l times, resulting in O(n^(l*l)), where l is the length of the words and thus the side length of the square.

Space Complexity

O(N) – The primary auxiliary space usage comes from storing the partially constructed word square during the recursive calls. In the worst case, the depth of the recursion can be equal to the length of each word (which is also the number of words needed to form the square), denoted as N. Each level of recursion stores a list of words of length N, so the space used is proportional to N * length of word, but since the length of each word is N, it simplifies to N. Thus the space complexity is O(N).

Optimal Solution

Approach

The key is to avoid checking every possible combination of words. We use a dictionary-like structure to quickly find words that *could* fit based on what we already have, and then intelligently build our word square line by line.

Here's how the algorithm would work step-by-step:

Imagine we're building a word square one row at a time. For the first row, we can pick any word from our list.
Now, for the second row, the *first* letter must match the *second* letter of the word we chose for the first row. We need a way to quickly find all words that start with that specific letter.
We create a special lookup table at the beginning that tells us, for every possible starting sequence (a single letter, two letters, three letters, etc.), all the words that begin with that sequence.
As we build each row, we use this lookup table to find only the words that are *possible* candidates for the next row, given the letters from the previous rows. This dramatically reduces the number of options we need to consider.
If, at any point, our lookup table shows that there are *no* words that fit the pattern, we know immediately that our current path won't work, and we can backtrack to try a different option.
Once we've successfully built all the rows to form a valid word square, we add it to our collection of solutions.

Code Implementation

def wordSquares(words):
    word_length = len(words[0])
    result = []

    # Create the prefix map for quick lookup.
    prefix_map = {}
    for word in words:
        for i in range(1, word_length + 1):
            prefix = word[:i]
            if prefix not in prefix_map:
                prefix_map[prefix] = []
            prefix_map[prefix].append(word)

    def backtrack(current_square):
        if len(current_square) == word_length:
            result.append(current_square[:])
            return

        # Determine the prefix for the next word.
        prefix_to_match = "".join([word[len(current_square)] for word in current_square])

        #Early termination if no words match current prefix
        if prefix_to_match not in prefix_map:
            return

        #Explore all matching prefixes to find the valid word square.
        for next_word_candidate in prefix_map[prefix_to_match]:
            current_square.append(next_word_candidate)
            backtrack(current_square)
            current_square.pop()

    #Iterate to pick different starting words.
    for word in words:
        backtrack([word])

    return result

Big(O) Analysis

Time Complexity

O(N * L^(L-1)) – Let N be the number of words in the input list and L be the length of each word. The time complexity is dominated by the recursive search for valid word squares. In the worst case, for each of the N words, we explore all possible combinations of words of length L for the remaining L-1 rows. Thus, we iterate up to N in the beginning, and then up to N^(L-1) in the recursive calls to build all rows. However, the prefix hashmap allows us to only explore words that match the prefix, reducing the number of branches explored. This makes the worst case N * (number of words starting with certain prefixes ^ (L-1)). Approximating number of words starting with certain prefixes with L, the runtime can be expressed as O(N * L^(L-1))

Space Complexity

O(N*L) – The auxiliary space is primarily determined by the lookup table, which maps prefixes to lists of words. In the worst case, every prefix of every word could be unique, leading to storing all N words in the input. Each word has a length of at most L, where L is the length of the longest word. Therefore, the space needed for the lookup table can be up to O(N*L), where N is the number of words and L is the maximum length of a word. Furthermore, the solution uses recursion, and the maximum depth of the recursion is the length of a word. However the space due to recursion stack is at most O(L) which is less than O(N*L). Hence the dominant space complexity remains O(N*L).

Edge Cases

Case	How to Handle
Empty input word list	Return an empty list immediately as no word square is possible.
Input word list contains empty strings	Filter out empty strings from the input list to avoid incorrect prefix matching.
Input word list contains strings of varying lengths	Only consider word lists where all words have the same length; otherwise, return an empty list.
No valid word square exists for the given input	The backtracking algorithm should explore all possibilities and return an empty list if no solution is found.
Word list contains duplicate words	The algorithm should correctly handle duplicate words, potentially leading to multiple valid word squares or no valid square at all, depending on the other words.
Maximum word length or word list size leading to stack overflow during recursion	Implement iterative deepening depth-first search or consider memoization to limit recursion depth and prevent stack overflow.
Very large input word list and large word size impacting performance significantly	Optimize prefix searching using a Trie data structure to improve the efficiency of finding suitable words during backtracking.
Integer overflow when calculating string hash if used for Trie operations	Use appropriate data types and modulo operations or choose a more robust hashing algorithm to prevent integer overflow.

Empty input word list

How to Handle:

Return an empty list immediately as no word square is possible.

Input word list contains empty strings

How to Handle:

Filter out empty strings from the input list to avoid incorrect prefix matching.

Input word list contains strings of varying lengths

How to Handle:

Only consider word lists where all words have the same length; otherwise, return an empty list.

No valid word square exists for the given input

How to Handle:

The backtracking algorithm should explore all possibilities and return an empty list if no solution is found.

Word list contains duplicate words

How to Handle:

The algorithm should correctly handle duplicate words, potentially leading to multiple valid word squares or no valid square at all, depending on the other words.

Maximum word length or word list size leading to stack overflow during recursion

How to Handle:

Implement iterative deepening depth-first search or consider memoization to limit recursion depth and prevent stack overflow.

Very large input word list and large word size impacting performance significantly

How to Handle:

Optimize prefix searching using a Trie data structure to improve the efficiency of finding suitable words during backtracking.

Integer overflow when calculating string hash if used for Trie operations

How to Handle:

Use appropriate data types and modulo operations or choose a more robust hashing algorithm to prevent integer overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of a word in the input list, and what is the maximum number of words in the input list?
Can the input list contain empty strings, null values, or words with different lengths?
If multiple word squares are possible, is any valid word square acceptable, or is there a specific ordering or criteria for selecting one?
If no word square is possible given the input, what should the return value be (e.g., an empty list, null)?
Are the words case-sensitive, or should I treat them as case-insensitive?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by picking a word for the first row of the square.
For the second row, try every word from the list. See if the first letter of this word matches the second letter of the first row word.
If it doesn't match, discard this word and try the next one.
If it does match, proceed to select a word for the third row, and check if its first two letters match the third letter of the first row word and the third letter of the second row word, respectively. Repeat this process.
Continue this pattern, row by row, checking if each word aligns correctly with the letters above it.
If at any point the letters don't align, backtrack and try a different word for that row.
When you have formed a complete square where all the letters align correctly both across rows and down columns, you've found a solution. Save that word square.
Repeat this entire process, starting with a different word for the first row, until all possible combinations have been tried.

Code Implementation

def find_word_squares_brute_force(words):
    results = []
    word_length = len(words[0]) if words else 0

    def backtrack(current_square):
        if len(current_square) == word_length:
            results.append(current_square[:])
            return

        # Iterate over all words to find a suitable candidate for the next row
        for word in words:
            if is_valid_word(current_square, word):
                current_square.append(word)
                backtrack(current_square)
                current_square.pop()

    def is_valid_word(current_square, word):
        row_index = len(current_square)

        # Ensures the new word aligns vertically with existing words
        for column_index in range(row_index):
            if current_square[column_index][row_index] != word[column_index]:
                return False
        return True

    # Start the search with each word as the first row
    for word in words:
        backtrack([word])

    return results

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine we're building a word square one row at a time. For the first row, we can pick any word from our list.
Now, for the second row, the *first* letter must match the *second* letter of the word we chose for the first row. We need a way to quickly find all words that start with that specific letter.
We create a special lookup table at the beginning that tells us, for every possible starting sequence (a single letter, two letters, three letters, etc.), all the words that begin with that sequence.
As we build each row, we use this lookup table to find only the words that are *possible* candidates for the next row, given the letters from the previous rows. This dramatically reduces the number of options we need to consider.
If, at any point, our lookup table shows that there are *no* words that fit the pattern, we know immediately that our current path won't work, and we can backtrack to try a different option.
Once we've successfully built all the rows to form a valid word square, we add it to our collection of solutions.

Code Implementation

def wordSquares(words):
    word_length = len(words[0])
    result = []

    # Create the prefix map for quick lookup.
    prefix_map = {}
    for word in words:
        for i in range(1, word_length + 1):
            prefix = word[:i]
            if prefix not in prefix_map:
                prefix_map[prefix] = []
            prefix_map[prefix].append(word)

    def backtrack(current_square):
        if len(current_square) == word_length:
            result.append(current_square[:])
            return

        # Determine the prefix for the next word.
        prefix_to_match = "".join([word[len(current_square)] for word in current_square])

        #Early termination if no words match current prefix
        if prefix_to_match not in prefix_map:
            return

        #Explore all matching prefixes to find the valid word square.
        for next_word_candidate in prefix_map[prefix_to_match]:
            current_square.append(next_word_candidate)
            backtrack(current_square)
            current_square.pop()

    #Iterate to pick different starting words.
    for word in words:
        backtrack([word])

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input word list	Return an empty list immediately as no word square is possible.
Input word list contains empty strings	Filter out empty strings from the input list to avoid incorrect prefix matching.
Input word list contains strings of varying lengths	Only consider word lists where all words have the same length; otherwise, return an empty list.
No valid word square exists for the given input	The backtracking algorithm should explore all possibilities and return an empty list if no solution is found.
Word list contains duplicate words	The algorithm should correctly handle duplicate words, potentially leading to multiple valid word squares or no valid square at all, depending on the other words.
Maximum word length or word list size leading to stack overflow during recursion	Implement iterative deepening depth-first search or consider memoization to limit recursion depth and prevent stack overflow.
Very large input word list and large word size impacting performance significantly	Optimize prefix searching using a Trie data structure to improve the efficiency of finding suitable words during backtracking.
Integer overflow when calculating string hash if used for Trie operations	Use appropriate data types and modulo operations or choose a more robust hashing algorithm to prevent integer overflow.

Empty input word list

How to Handle:

Return an empty list immediately as no word square is possible.

Input word list contains empty strings

How to Handle:

Filter out empty strings from the input list to avoid incorrect prefix matching.

Input word list contains strings of varying lengths

How to Handle:

Only consider word lists where all words have the same length; otherwise, return an empty list.

No valid word square exists for the given input

How to Handle:

The backtracking algorithm should explore all possibilities and return an empty list if no solution is found.

Word list contains duplicate words

How to Handle:

The algorithm should correctly handle duplicate words, potentially leading to multiple valid word squares or no valid square at all, depending on the other words.

Maximum word length or word list size leading to stack overflow during recursion

How to Handle:

Implement iterative deepening depth-first search or consider memoization to limit recursion depth and prevent stack overflow.

Very large input word list and large word size impacting performance significantly

How to Handle:

Optimize prefix searching using a Trie data structure to improve the efficiency of finding suitable words during backtracking.

Integer overflow when calculating string hash if used for Trie operations

How to Handle:

Use appropriate data types and modulo operations or choose a more robust hashing algorithm to prevent integer overflow.