425. Word Squares

How to solve Word Squares (LeetCode 425): the approach in brief

The problem

Given a set of words (without duplicates), find all word squares you can build from them.

Pattern

Word Squares is a Design Patterns problem, in the Tries subpattern. The pattern covers tries, LRU/LFU cache, and data structure design

Implement Trie data structure for prefix-based operations and autocomplete systems.

Approach outline

1. Consider using backtracking to build word squares by adding one word at a time and checking validity at each step.
2. To efficiently find candidate words that can fit in the next row, think about how to quickly retrieve words with a specific prefix.
3. Building a Trie from the input words allows you to search for all words starting with a given prefix in O(1) time per character, which can optimize prefix lookups during backtracking.

Complexity

The reference solution runs in O(n^2 * n!) time and O(n^2) space.

Asked at

Word Squares has been reported in interviews at Bloomberg.