Algorithm for searching grid in diffrent direction

views:

answers:

+2 Q:

Algorithm for searching grid in diffrent direction

Hi,

Today a work mate posed a question to me. Given a grid of characters and a list of words one would have to find every occurrence of that word in the grid both horizontally, vertically and diagonally.

The solution we came up with works and does the trick but I am interested to see how other peoples minds tick.

+4 A:

Insert each word in the list in a trie, or hash table or any dictionary.

Now, for each position in your grid, go horizontally, vertically and diagonally and see if you get matches in the dictionary. This should give you O(N^3) worst case complexity, where N is the size of the grid. Otherwise it's O(N^2*averageWordLength) I think.

IVlad 2010-07-14 14:29:45

Wouldn't it be `O(N*maxWordLength)`? Each letter only needs to be checked for being the start of a word of length 1, 2, 3, ..., maxWordLength.

BlueRaja - Danny Pflughoeft 2010-07-14 16:45:42

A hash table would be a poor choice compared to a trie. With the trie, once you don't get any matches for a string of length k you can stop. With a hash table you can't stop until you've tried all strings of length n (n is the distance from your char to the edge). For example, let's say you have the row (INTABCDE). The word INTEGER is in your dictionary. With the trie, you first try I, which is not in the dictionary but is a valid path. You continue until A, and you are no longer on a valid path. You can't do that with a hash table, so you would be forced to hash all possible strings.

Niki Yoshiuchi 2010-07-14 16:47:04

@BlueRaja - that's what I said too actually :). I meant `N` to be the size of an `N x N` grid (which therefore has `N^2` total elements). If you consider `N` to be the total number of elements in the grid, then it's `N` not `N^2`. @Niki - true.

IVlad 2010-07-14 17:34:04

Whoops missed that, sorry :)

BlueRaja - Danny Pflughoeft 2010-07-14 17:42:09

Boyer-Moore's is a nice alg for exact string matching

belisarius 2010-07-14 23:56:56

ansaurus

tags:

views:

answers:

Algorithm for searching grid in diffrent direction

related questions