0

Given a dictionary of millions of words, give an algorithm to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom).

I found a very nice solution here on stackoverflow. Basically, after I construct a Trie, I use backtracking to put all possible suffixes into the matrix until I find a valid one. However, I am stuck on how to write the backtracking part.

consider I have put 'a' in my matrix and 'a' has 3 children 'b', 'c' and 'd'.

a * ? ?
* ? ? ? 
? ? ? ?
? ? ? ?

So I need to put 'b' into the matrix and check 'b's children. If it doesn't work, I need to remove one 'b' and put 'c' into the matrix, and so on. So it should be like this:

a * ? ?           a b * ?                                     a b * ?
* ? ? ?     ->    b * ? ?     (if anything doesn't work) ->   c * ? ? 
? ? ? ?           * ? ? ?                                     * ? ? ?
? ? ? ?           ? ? ? ?                                     ? ? ? ?

How should I implement this? Thank you.

Community
  • 1
  • 1
DoraShine
  • 659
  • 1
  • 6
  • 11

1 Answers1

0

Well, I still couldn't figure out that solution, but I have another bloody brutal one. It's still a backtracking one and it still needs Trie. Basically, I put all strings that need to form the columns into the Trie. Add each string in the row set, check if every prefix formed by the column is contained in the Trie, if not, continue, otherwise, recursively adding row string until we find the matrix. Please take a look at my blog for details and let me know if you have any questions.

DoraShine
  • 659
  • 1
  • 6
  • 11