O(n) of solution to solve boggle

Question

What is the best time complexity O(n) of a function that solves boggle, where the boggle board is n by n?

I feel that it's n^2 since for each character we must look at 2(n-1) other characters. The interviewer argued that it's not n^2 for an O(1) dictionary look-up.

Answer 1

I finally figured it out. The answer turns out to be exponential in time.

Imagine a 4X4 boggle grid

ABCD
EFGH
IJKL
MNOP

Then for example, any of the ordered subsequences starting with A in ABCDHGFEIJKLPONM is a potential word; so is any of the ordered subsequences starting with A in AEIMNOPLHDCBFJKG or AEIMNOPLHGFIK or ABCDHLPONMIEFGKJ. Then we need to look at the potential words starting wiht B, then with C, etc.

Let's look at this another way. Say we only had to consider _ABCD, where _ represents some starting character, say X; then the potential words belong to the power set are:

XD; XC; XCD; XB; XBD; etc.

Hence, considering only the clockwise spirals starting at each character, we are already looking at n^2*2^(n-1). n^2 because the grid is n by n and so for a 4 by 4 grid there are 16 possible starting characters. And 2^(n-1) because of the powerset led by each starting character. Of course the clockwise spiral is not the only possible pattern. But we can already see the time complexity with that first pattern: Big-Omega(2^n) which is exponential.

Answer 2

It's not very clear what the dictionary is capable of.

A bit silly but in my opinion correct answer is as follows:

Since in boggle, words can go arbitrary ways (from each character to any adjacent (horizontal, vertical or diagonal) characters not already used in this word), for a word of length L, the cominations of words can be up to 8^L unless you eliminate the combinations where characters appear multiple times. Anyway, considering L to be constant (as the used dictionary is constant), this value is constant too. To sum up, finding word(s) starting from a given position has a time complexity of O(1).

So what remains is the start position of the word, which is in the space n^2, so your boggle solver has time complexity of O(n^2) and you are right.

As said before, I think this argumentation is a bit silly.

The problem might be that one doesn't want to consider the dictionary to be constant, because it is very large. Assuming it to be infinitely large but it implements a O(1) look-up for existing words (which is the ONLY query we can use for the dictionary, especially there is no look-up for word prefixes), and further assuming n not to be a limiting factor in comparison to the word lengths, time complexity is exponential. But I think the assumption that the look-up only succeeds for existing words is false in this exercise.

Another possible assumption would be, that the dictionary has a look-up for word prefixes (which returns whether there exist words which start with the given string but are not necessarily equal to the string). In this case, we could implement a better and far more complex algorithm which searches the limited search space (using each character at most once). A limiting factor of word lengths would be n^2, since no word (contained in the current boggle board) can be longer than that (because we can use each character only once). Again the start positions are in space n^2, so a stupid path-based algorithm would have a time complexity of O(n^4), so you are wrong. Currently, I can't think of an algorithm with better time complexity under this assumptions.

Answer 3

Take a look at http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html. The dynamic programming solution is O(D) where D is the size of a dictionary.