Last Updated: 14 Mar, 2021

Word Squares

Hard

Asked in companies

Solve now

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(NUM_ROWS, NUM_COLUMNS). You can return word square in any order.

Note:

1) All words will have the exact same length.
2) Each word contains only lowercase English alphabet a-z.

Example:

The word sequence ["ball", "area", "lead", "lady"] forms a word square because each word reads the same both horizontally and vertically i.e.
b a l l
a r e a
l e a d
l a d y

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains one integer ‘N’ where ‘N’ denotes the number of strings.

The second line of every test case contains ‘N’ space-separated strings.

Output format:

For each test case, return all the valid word squares you can build from the string array.

Note:

1) You do not need to print anything, it has already been taken care of. Just return all the valid word squares.

Constraints:

1 <= T <= 10
1 <= N <= 10^3
1 <= |WORD| <= 5

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

The basic idea is to take a word from the given word list one by one as the first word of word squares, and then find the prefix of the next word in word squares according to the current word, and then find the corresponding word according to the prefix found.
So there are two parts. The first part is to find the words starting with word square one by one in the given word list, that is, start with the current word; the second part is to connect based on the selected first word that is which words should be put in the word square to make the whole result form a legal word square.

Algorithm:

Firstly declare a 2d vector of string ‘RESULT’ to store the result.
Iterate over the vector of words and for each word call the ‘GET_PREFIX’ function.
Inside the ‘GET_PREFIX’ function:
- Create a Hashmap ‘PREFIX_MAP’ to store the prefixes of all the words such that key will be the prefix and the value is a list of words with that prefix. Find the prefix of each word.
Iterate through all the words again and for each word in the wordList
- create a new list ‘SQUARE’. Add that word to the list ‘SQUARE’.
- Call the recursive function ‘GET_SQUARES’ with PARAMETERS (START_INDEX, SQUARE, RESULT). Here ‘START_INDEX’ will have a value = 1 initially as ‘START_INDEX’ indicates how many words are put in the current path after selecting the first word at the beginning.
Inside the ‘GET_SQUARES’ function:
- Find the prefix.
- Search the ‘PREFIX_MAP’ for all the words that have the correct prefix.
- For each of these words
  - Add it to the list.
  - Continue searching for the next prefix recursively.
The recursion reaches its base case when the size of the list is equal to the length of a word. In this case, we've found a word square and return ‘RESULT’ as the answer.

EXAMPLE:

Let's say we have words array = {"area","lead","wall","lady","ball"}

We know that the sequence contains 4 words because the length of each word is 4.

Every word can be the first word of the sequence, let's take "wall" for example.

Which word could be the second word? Must be a word starting with "a" (therefore "area"), because it has to match the second letter of the word "wall".

Which word could be the third word? Must be a word starting with "le" (therefore "lead"), because it has to match the third letter of the word "wall" and the third letter of the word "area".

What about the last word? Must be a word starting with "lad" (therefore "lady"). For the same reason above.

Solve now