We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Squares

Number: 425

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given an array of unique words (all of the same length), you need to build all possible word squares. A word square is a sequence of words arranged in a square so that the kth row and kth column read the same string. Note that the same word may be used multiple times in constructing a square.

Key Insights

  • Use backtracking to construct candidate word squares one row at a time.
  • For each new row, determine the required prefix (formed from the kth letters of previously chosen words) that the candidate word must match.
  • Precompute a mapping (or Trie) from prefixes to the list of words that share that prefix. This allows efficient lookup and pruning.
  • The problem leverages the fact that all words have the same length and the board is square.

Space and Time Complexity

Time Complexity: In the worst-case, it can be exponential due to backtracking. However, using prefix lookups significantly prunes the search. With L as the word length and N as the number of words, the effective time complexity is approximately O(N * L * (number of candidates per prefix)^(L)). Space Complexity: O(N * L) for the prefix mapping, plus O(L) for the recursion stack and building the current square.

Solution

This solution uses backtracking combined with a prefix mapping technique. First, we precompute a dictionary that maps every possible prefix to the list of words with that prefix. Then we start forming a word square row-by-row. At each recursive call, we derive the prefix for the next word based on the current square (by taking the ith character from each of the already chosen words where i is the current depth). We then only consider words that match this prefix. This drastically reduces the number of possibilities, making the backtracking efficient even for multiple words. The algorithm uses recursive DFS (depth-first search) and backtracking to explore valid combinations and build complete word squares.

Code Solutions

# Python solution for Word Squares

class WordSquares:
    def __init__(self, words):
        self.N = len(words[0])
        self.words = words
        self.prefix_map = {}
        # Build prefix mapping: for every prefix, map to list of words with that prefix.
        for word in words:
            for i in range(len(word) + 1):
                prefix = word[:i]
                if prefix in self.prefix_map:
                    self.prefix_map[prefix].append(word)
                else:
                    self.prefix_map[prefix] = [word]

    def find_word_squares(self):
        results = []
        square = []
        # Begin backtracking starting with each word.
        for word in self.words:
            square = [word]
            self.backtrack(1, square, results)
        return results

    def backtrack(self, step, square, results):
        # If the current square is complete, add a copy to results
        if step == self.N:
            results.append(list(square))
            return
        
        # Build the prefix for the next word in the square using the kth letter of each current word.
        prefix = ''.join([word[step] for word in square])
        for candidate in self.prefix_map.get(prefix, []):
            square.append(candidate)
            self.backtrack(step + 1, square, results)
            square.pop()  # backtrack if no valid square found

# Example usage:
# words = ["area", "lead", "wall", "lady", "ball"]
# ws = WordSquares(words)
# print(ws.find_word_squares())
← Back to All Questions