Make delicious recipes!

Largest rectangle of words


Given a dictionary of words, create a rectangle of alphabets such that every row (from left to right) forms a
valid word and every column (from top to bottom) forms a valid word.

Examples:
cat
are
pea

slam
nice
over
west

Solution: Since its a rectangle, all the words must be of the same length.

So first task here should be to separate words into groups such that same length words fall into the same group.

This can be done by creating a HashMap<Integer,Set<String>> of word-length vs set of words.

We can then iterate over each group of words to begin the main task of finding the largest rectangle.

One way to find the rectangle is to take a word and see if all its characters also form prefixes of other words.

If it does, then it could become the first word of a valid rectangle.

On finding such a word, iterate over all other words, put each word in the second place and see if every two-letter combination
for every column forms a prefix in the dictionary. If not, then that choice of second word can be discarded.
This can be continued to get a closure on third word (by comparing each 3-letter string for prefixes in the dictionary) and so on.

If there are N words in any group, there can be potentially 2N combinations and this approach would try them all.
Not a very good solution!




We need to explore some properties of the rectangle to reduce the problem.
See the highlighted alphabets in this rectangle.
slam
nice
over
west

First diagonal alphabet must be first alphabet in atleast two words.
Second diagonal alphabet must be second alphabet in atleast two words.
Similarly, nth alphabet must be nth alphabet in atleast two words.


This is a good reduction and we can reduce it even further.
slam
nice
over
west

A word is fit to be second word if its third alphabet forms a valid prefix of 2 alphabets with the alphabet immediately above it.
(Talking about letter 'c' in 'nice')

Generally speaking, matrix[i][j] is a valid alphabet in the solution if forms two valid prefixes - Left-to-Right and Top-to-Bottom

To efficiently look for prefixes, we build a trie of all the words and apply the following algorithm.
For word-size from Largest-Word.length() to Smallest-Word.length()
  1. Put an alphabet at matrix[i][j] if it forms two valid prefixes.
  2. If word-size is reached in a row, begin placing alphabets from the next row.
  3. If no alphabets can be found for (i,j), remove previously chosen alphabet and backtrack.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal