Word Squares - Practice Coding Problems

Word Squares - Problem

Given an array of unique strings words, return all the word squares you can build from words. The same word from words can be used multiple times. You can return the answer in any order.

A sequence of strings forms a valid word square if the k-th row and column read the 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

Notice that words[0][0] = words[0][0], words[0][1] = words[1][0], words[0][2] = words[2][0], and so on.

Input & Output

Example 1 — Perfect Word Square

$ Input: words = ["area","lead","wall","lady","ball"]

› Output: [["ball","area","lead","lady"]]

💡 Note: The word square is: b-a-l-l, a-r-e-a, l-e-a-d, l-a-d-y. Each row equals its corresponding column: ball/ball, area/area, lead/lead, lady/lady.

Example 2 — No Valid Square

$ Input: words = ["abat","baba","atan","atal"]

› Output: []

💡 Note: No combination of these words can form a valid word square where each row matches its corresponding column.

Example 3 — Single Character Words

$ Input: words = ["a","b"]

› Output: [["a"],["b"]]

💡 Note: Single character words automatically form valid 1x1 word squares.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words of equal length

Arrange

Form square where word[i][j] = word[j][i]

Validate

Check that each row equals its column

Key Takeaway

🎯 Key Insight: Build squares incrementally using backtracking with prefix-based pruning for efficiency

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is to use backtracking with prefix-based pruning to efficiently build word squares row by row. Best approach uses a trie or prefix map for O(1) prefix lookups. Time: O(n^n), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Backtracking	O(n^n × n²)	O(n² × result_count)	Try all combinations and validate each complete square
Optimized Backtracking with Prefix Pruning	O(n^n)	O(n²)	Use backtracking with early pruning based on prefix matching

Brute Force Backtracking — Algorithm Steps

Generate all combinations of words
For each combination, check if it forms a valid word square
Add valid squares to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible combinations of words

Validate

Check if each combination forms a valid word square

Collect

Store valid word squares in result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 50
#define MAX_LEN 10
#define MAX_RESULTS 1000

char words[MAX_WORDS][MAX_LEN];
char results[MAX_RESULTS][MAX_WORDS][MAX_LEN];
int result_count = 0;
int word_count = 0;
int word_len = 0;

bool isValidWordSquare(char square[][MAX_LEN], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (square[i][j] != square[j][i]) {
                return false;
            }
        }
    }
    return true;
}

void backtrack(char current[][MAX_LEN], int depth) {
    if (depth == word_len) {
        if (isValidWordSquare(current, word_len)) {
            for (int i = 0; i < word_len; i++) {
                strcpy(results[result_count][i], current[i]);
            }
            result_count++;
        }
        return;
    }
    
    for (int i = 0; i < word_count; i++) {
        strcpy(current[depth], words[i]);
        backtrack(current, depth + 1);
    }
}

void solution() {
    if (word_count == 0) return;
    
    char current[MAX_WORDS][MAX_LEN];
    backtrack(current, 0);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array
    char* ptr = line + 1; // Skip '['
    char* token = strtok(ptr, ",");
    
    while (token != NULL && word_count < MAX_WORDS) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == ']')) end--;
        *(end + 1) = 0;
        
        strcpy(words[word_count], token);
        if (word_count == 0) word_len = strlen(token);
        word_count++;
        token = strtok(NULL, ",");
    }
    
    solution();
    
    printf("[");
    for (int i = 0; i < result_count; i++) {
        printf("[");
        for (int j = 0; j < word_len; j++) {
            printf("\"%s\"", results[i][j]);
            if (j < word_len - 1) printf(",");
        }
        printf("]");
        if (i < result_count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^n × n²)

Generate n^n combinations, each requiring O(n²) validation

⚠ Quadratic Growth

Space Complexity

O(n² × result_count)

Store result squares and recursion stack

⚠ Quadratic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler