2

Given a dictionary of words, two APIs Is_word(string) Is_prefix(string) And a NxN matrix with each postion consisting of a character. If from any position (i,j) you can move in any of the four directions, find out the all the valid words that can be formed in the matrix. (looping is not allowed, i.e. for forming a word position if you start from (i,j) and move to (i-1,j) then from this position you cannot go back to (i,j))

What I trie :: I can see an exponential solution where we go though all possibilities and Keep track of already visited Indexes. Can we have a better solution?

user973931
  • 515
  • 1
  • 4
  • 13
  • So you want to solve a boggle-like game? http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver – argentage Jul 13 '12 at 04:38

3 Answers3

2

This is the best I can do:

  1. Enumerate all the possible strings in half of the allowed directions. (You can reverse the strings to get the other directions.)
  2. For each starting character position in each string, build up substrings until they are neither a word nor a prefix.

Edit: I may have misunderstood the question. I thought each individual word could only be made up of moves in the same direction.

Neil
  • 54,642
  • 8
  • 60
  • 72
  • Just using half of the allowed directions and reversing the strings will not yield all possible solutions. What if there is a string constructed by taking the following path from the start letter: `EAST -> SOUTH -> WEST`. This string could not possibly be constructed by only using two of the allowed directions. – Alderath Jul 17 '12 at 13:23
0

I would be inclined to solve this by creating two parallel data structures. One is a list of words (where duplicates are removed). The other is a matrix of prefixes, where each element is a list. Hopefully, such data structures can be used. The matrix of lists could really be a list of triplets, with the word and coordinates in the original matrix.

In any case, go through the original matrix and call isword() on each element. If a word, then insert the word into the word list.

Then go through the original matrix, and compare call isprefix() on each element. If a prefix, insert in the prefix matrix.

Then, go through the prefix matrix and test the four combinations of the prefix with the additional letter. If a word, then put in word list. If a prefix, then add to the prefix matrix, in the location of the last letter. Remember to do both, since a word can be a prefix.

Also, in the prefix list, you need to keep a list not only of the letters, but the locations of the letters that have been used. This is used to prevent loops.

Then continue this process until there are no words and no prefixes.

It is hard to measure the complexity of this structure, since it seems to depend on the contents of the dictionary.

Gordon Linoff
  • 1,242,037
  • 58
  • 646
  • 786
0

I think you can't beat exponential here. Proof?

Think about the case when you have a matrix where you have arrangement of letters such that each combination is a valid dictionary word i.e. when you start from [i,j] for e.g. [i,j] combined with either [i-1,j] or [i+1,j] or [i,j+1] or [i,j-1] are all 2 letter words and that continues recursively i.e. any combination of length n (according to your rules) is a word. In this case you can't do better than a brute force.

user1168577
  • 1,863
  • 11
  • 14