425. Word Squares
Word Squares (LeetCode 425) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Tries subpattern.
How to solve Word Squares
Word Squares is a Trie Implementation problem, part of Design Patterns. Implement Trie data structure for prefix-based operations and autocomplete systems.
Work towards the solution in these steps:
- Consider using backtracking to build word squares by adding one word at a time and checking validity at each step.
- To efficiently find candidate words that can fit in the next row, think about how to quickly retrieve words with a specific prefix.
- 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.
The reference solution runs in O(n^2 * n!) time and O(n^2) space.
The Word Squares solution and editorial walks through the full approach with reference code.
Problem statement
Given a set of words (without duplicates), find all word squares you can build from them.
A sequence of words forms a valid word square if the kth 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 Note: There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z.
Example 1: Input: ["area","lead","wall","lady","ball"] Output: [ [ "wall", "area", "lead", "lady" ], [ "ball", "area", "lead", "lady" ] ] Explanation: The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Example 2: Input: ["abat","baba","atan","atal"] Output: [ [ "baba", "abat", "baba", "atan" ], [ "baba", "abat", "baba", "atal" ] ] Explanation: The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Topics and companies
Topics: Backtracking, Trie.
Reported in interviews at Bloomberg.
How to practise Word Squares on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2 * n!) time and O(n^2) space.
Open Word Squares in the code editor, or read the Word Squares editorial for a worked solution with its approach and complexity analysis.
Where Word Squares sits in the DSA pattern sheet
Problems related to Word Squares
Other problems that use the same Tries and Design Patterns techniques:
- Design Add and Search Words Data Structure — Medium, same subpattern
- Extra Characters in a String — Medium, same subpattern
- Implement Trie (Prefix Tree) — Medium, same subpattern
- Longest Word in Dictionary — Easy, same subpattern
- Prefix and Suffix Search — Hard, same subpattern
- Replace Words — Medium, same subpattern
Word Squares FAQ
What is the LeetCode number of Word Squares?
Word Squares is LeetCode problem 425, rated Hard.
What pattern is used to solve Word Squares?
Word Squares is a Trie Implementation problem. It belongs to the Design Patterns pattern, in the Tries subpattern.
What is the time complexity of Word Squares?
The reference solution runs in O(n^2 * n!) time and O(n^2) space.
Which companies ask Word Squares?
Word Squares has been reported in interviews at Bloomberg.