Word Squares II solution and explanation
5 more videos on this problem
Leetcode 3799. Word Squares II | Set | Brute force approach | 2D Array | MediumLeet's Code · 20:17 · 270 views
LeetCode 3799 | Word Squares II | Weekly Contest 483 | JavaCode Kage · 10:43 · 258 views
Word Squares II | LeetCode 3799 | Weekly Contest 483 | Java Code | Developer CoderDeveloper Coder · 11:13 · 222 views
3799. Word Squares II (Leetcode Medium)Programming Live with Larry · 6:43 · 108 views
LeetCode 3799 Word Squares II & 3798 Largest Even Number | DSA Interview Prep | JavaProof2Code · 13:55 · 90 views
3799. Word Squares II | leetcode weekly contest 483CodingHelp · 11:39 · 36 views
The problem
You are given a string array words, consisting of distinct 4-letter strings, each containing lowercase English letters.
A word square consists of 4 distinct words: top, left, right and bottom, arranged as follows:
topforms the top row.bottomforms the bottom row.leftforms the left column (top to bottom).rightforms the right column (top to bottom).
It must satisfy:
top[0] == left[0],top[3] == right[0]bottom[0] == left[3],bottom[3] == right[3]
Return all valid distinct word squares, sorted in ascending lexicographic order by the 4-tuple (top, left, right, bottom).
Example 1:
Input: words = ["able","area","echo","also"]
Output: [["able","area","echo","also"],["area","able","also","echo"]]
Explanation:
There are exactly two valid 4-word squares that satisfy all corner constraints:
"able"(top),"area"(left),"echo"(right),"also"(bottom)top[0] == left[0] == 'a'top[3] == right[0] == 'e'bottom[0] == left[3] == 'a'bottom[3] == right[3] == 'o'
"area"(top),"able"(left),"also"(right),"echo"(bottom)- All corner constraints are satisfied.
Thus, the answer is [["able","area","echo","also"],["area","able","also","echo"]].
Example 2:
Input: words = ["code","cafe","eden","edge"]
Output: []
Explanation:
No combination of four words satisfies all four corner constraints. Thus, the answer is empty array [].
Constraints:
4 <= words.length <= 15words[i].length == 4words[i]consists of only lowercase English letters.- All
words[i]are distinct.
Approach overview
Problem Overview: You are given a list of words where each word has the same length. The task is to construct all possible word squares. A word square is a sequence of words such that the kth row and kth column read the same string. For example, the first word defines the first column, the second word must match the second column prefix, and so on.
Approach 1: Brute Force Enumeration (O(N! * L^2) time, O(L) space)
The naive idea is to try every possible ordering of words and check whether they form a valid square. Generate permutations using recursion or iterative enumeration, then validate the grid by comparing characters at grid[i][j] and grid[j][i]. Validation takes O(L^2) for word length L. This approach quickly becomes infeasible because permutations grow factorially with the number of words. It is mainly useful for understanding the structural constraint of word squares.
Approach 2: Backtracking with Prefix Hash Map (O(N * L^2 * B) time, O(N * L) space)
A more practical approach builds the square row by row using backtracking. When placing the kth word, the prefix formed by characters square[0][k], square[1][k], ..., square[k-1][k] must match the start of the candidate word. Precompute a prefix lookup table using a hash map where each prefix maps to all words that start with it. During recursion, compute the required prefix and fetch valid candidates in constant time. This prunes most invalid branches early, making the search manageable.
The algorithm iterates through each word as a starting row, then recursively fills the next rows while maintaining the prefix constraint. The prefix map is built by iterating through every word and storing prefixes of length 1..L. The recursion depth is at most L, and each step narrows candidates using prefix filtering. This combines string prefix matching with array style indexing for column validation.
Approach 3: Backtracking with Trie Prefix Search (O(N * L^2 * B) time, O(N * L) space)
Instead of a hash map, store all words in a Trie. Each Trie node tracks the indices of words that share the prefix represented by that node. While building the square, traverse the Trie using the required prefix and immediately retrieve candidate words. This reduces repeated prefix scans and keeps lookup efficient even when the dictionary is large.
Recommended for interviews: Backtracking with prefix lookup (hash map or Trie) is the expected solution. Interviewers want to see that you identify the prefix constraint and prune the search tree early. Starting with the brute-force permutation idea shows you understand the problem structure, but switching to prefix-guided backtracking demonstrates algorithmic optimization and practical search design.
Solution
class Solution:
def wordSquares(self, words: List[str]) -> List[List[str]]:
words.sort()
n = len(words)
ans = []
for i in range(n):
top = words[i]
for j in range(n):
if j != i:
left = words[j]
for k in range(n):
if k != j and k != i:
right = words[k]
for h in range(n):
if h != k and h != j and h != i:
bottom = words[h]
if (
top[0] == left[0]
and top[3] == right[0]
and bottom[0] == left[3]
and bottom[3] == right[3]
):
ans.append([top, left, right, bottom])
return ansclass Solution {
public List<List<String>> wordSquares(String[] words) {
Arrays.sort(words);
int n = words.length;
List<List<String>> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
String top = words[i];
for (int j = 0; j < n; j++) {
if (j != i) {
String left = words[j];
for (int k = 0; k < n; k++) {
if (k != j && k != i) {
String right = words[k];
for (int h = 0; h < n; h++) {
if (h != k && h != j && h != i) {
String bottom = words[h];
if (top.charAt(0) == left.charAt(0)
&& top.charAt(3) == right.charAt(0)
&& bottom.charAt(0) == left.charAt(3)
&& bottom.charAt(3) == right.charAt(3)) {
ans.add(List.of(top, left, right, bottom));
}
}
}
}
}
}
}
}
return ans;
}
}class Solution {
public:
vector<vector<string>> wordSquares(vector<string>& words) {
ranges::sort(words);
int n = words.size();
vector<vector<string>> ans;
for (int i = 0; i < n; i++) {
string top = words[i];
for (int j = 0; j < n; j++) {
if (j != i) {
string left = words[j];
for (int k = 0; k < n; k++) {
if (k != j && k != i) {
string right = words[k];
for (int h = 0; h < n; h++) {
if (h != k && h != j && h != i) {
string bottom = words[h];
if (top[0] == left[0] && top[3] == right[0] && bottom[0] == left[3] && bottom[3] == right[3]) {
ans.push_back({top, left, right, bottom});
}
}
}
}
}
}
}
}
return ans;
}
};function wordSquares(words: string[]): string[][] {
words.sort();
const n = words.length;
const ans: string[][] = [];
for (let i = 0; i < n; i++) {
const top = words[i];
for (let j = 0; j < n; j++) {
if (j !== i) {
const left = words[j];
for (let k = 0; k < n; k++) {
if (k !== j && k !== i) {
const right = words[k];
for (let h = 0; h < n; h++) {
if (h !== k && h !== j && h !== i) {
const bottom = words[h];
if (
top[0] === left[0] &&
top[3] === right[0] &&
bottom[0] === left[3] &&
bottom[3] === right[3]
) {
ans.push([top, left, right, bottom]);
}
}
}
}
}
}
}
}
return ans;
}func wordSquares(words []string) [][]string {
sort.Strings(words)
n := len(words)
ans := [][]string{}
for i := 0; i < n; i++ {
top := words[i]
for j := 0; j < n; j++ {
if j != i {
left := words[j]
for k := 0; k < n; k++ {
if k != j && k != i {
right := words[k]
for h := 0; h < n; h++ {
if h != k && h != j && h != i {
bottom := words[h]
if top[0] == left[0] &&
top[3] == right[0] &&
bottom[0] == left[3] &&
bottom[3] == right[3] {
ans = append(ans, []string{top, left, right, bottom})
}
}
}
}
}
}
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(N! * L^2) | O(L) | Only for very small input sizes or conceptual understanding of word square validation |
| Backtracking + Prefix Hash Map | O(N * L^2 * B) | O(N * L) | General case; fast prefix lookup prunes invalid branches during search |
| Backtracking + Trie | O(N * L^2 * B) | O(N * L) | Best when the dictionary is large and repeated prefix searches are frequent |
Frequently asked questions
Is Word Squares II easy or hard?
Word Squares II is generally considered a medium difficulty problem. The challenge comes from recognizing the prefix constraint and designing an efficient backtracking strategy with prefix indexing rather than brute-force permutations.
Word Squares II Python/Java solution
Typical implementations in Python or Java use recursive backtracking with a dictionary that maps prefixes to candidate words. Each recursive step constructs the required prefix from existing rows, retrieves matching words, and continues building the square until its size equals the word length.
How to solve Word Squares II in O(n)?
An overall O(n) solution is not feasible because the algorithm must explore combinations of words to build valid squares. The practical optimization is using prefix-based pruning with backtracking, which significantly reduces the search space but still depends on branching during recursion.
What is the best approach for Word Squares II?
Backtracking with prefix lookup is the most effective approach. Precompute a prefix map or Trie so that when building the square row by row, you can quickly find words that match the required column prefix. This prunes invalid branches early and keeps the search manageable.
Is Word Squares II asked at Google/Amazon/Meta?
Word square style problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test backtracking, prefix matching, and search pruning. Variants involving Trie structures or prefix maps are especially common.
What data structure is used in Word Squares II?
The core data structures are arrays or lists for building the square and a prefix lookup structure. Most implementations use a hash map from prefix to word list, while some optimized solutions use a Trie to retrieve candidates efficiently.
What is the time complexity of Word Squares II?
The optimized backtracking solution runs in roughly O(N * L^2 * B), where N is the number of words, L is the word length, and B is the average branching factor for valid prefixes. Space complexity is O(N * L) for storing prefix mappings or the Trie.