Write a program to find the largest possible rectangle of letters such that every row forms a word (left to right) and every column forms a word (top to bottom).
I found this interesting question. It's not homework, though it may sound as such. (I'm not in school). I'm doing this for fun.
Example
From cat, car, ape, api, rep, tip we get the following rectangle (which is a square):
c a r a p e t i p
My initial idea is to build a some sort of a prefix tree so I can retrieve all words that start with a specific string. This would be useful when we already have 2 or more words (either reading top to bottom or left to right) and we need to find the next word to add.
Any other ideas?
Edit
Could this be done with a cuboid (3D rectangle)?
What if it needs to have valid words on the diagonals (idea credit: user645466); how would the algo for it be optimized?