Word Squares

Hard
0/120
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
SamsungAmazon

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5
wall ball lead lady area
Sample Output 1:
wall
area
lead
lady

ball
area
lead
lady
Explanation 1:
For the first test case, 
The output consists of two word squares. As it is evident from the 
output that the kth row and the kth column contain the same 
word.The order of output does not matter just the order of words 
in each word square matters.
Sample Input 2:
1
4
abat baba atan atal
Sample Output 2:
 baba
 abat
 baba
 atan

 baba
 abat
 baba
 atal
Explanation 2:
For the first test case, 
The output consists of two word squares. As it is evident from the 
output that the kth row and the kth column contain the same 
word. The order of output does not matter just the order of words 
in each word square matters.
Hint

Solve this problem by first calculating the prefixes of each word and store them in HashMap. Then try to form a valid word square from every word present in the array(backtracking) using the Hashmap that we built.

Approaches (1)
Word Squares

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.

Time Complexity

O(N*L + N*26^L), where ‘N’ is the number of words and ‘L’ is the length of the longest prefix.

 

Traversing over ‘N’ words and calculating their prefixes will take O(N*L) time. Traversing again on the wordList and calling the recursive function ‘getSquares’ will take O(N*26^L).

Thus total time complexity will be O(N*L + N*26^L).

Space Complexity

O(N*L), where ‘N’ is the number of words and ‘L’ is the length of the longest prefix.

 

O(N*L) extra space is required for the Hashmap to store the prefixes. Also, O(L) extra space is required to store each string in a separate list. Hence, the overall space complexity is O(N*L). 

Code Solution
(100% EXP penalty)
Word Squares
Full screen
Console