Fun and games - Data Structures and Problem Solving Using Java - page 423

This algorithm rearranges the loop to avoid searching for every word in the word
list. If we assume that words are limited to 20 characters, the number of checks
used by the algorithm is 160 RC . For a 32

The lookups can be
done by a binary
search.

32 puzzle, this number is roughly
160,000 checks. The problem, of course, is that we must now decide whether a
word is in the word list. If we use a linear search, we lose. If we use a good data
structure, we can expect an efficient search. If the word list is sorted, which is to be
expected for an online dictionary, we can use a binary search (shown in
Figure 5.12) and perform each check in roughly string comparisons. For
40,000 words, doing so involves perhaps 16 comparisons per check, for a total of
less than 3,000,000 string comparisons. This number of comparisons can certainly
be done in a few seconds and is a factor of 100 better than the previous algorithm.

×

log W

We can further improve the algorithm based on the following observation.
Suppose that we are searching in some direction and see the character
sequence qx . An English dictionary will not contain any words beginning with
qx . So is it worth continuing the innermost loop (over all word lengths)? The
answer obviously is no: If we detect a character sequence that is not a prefix
of any word in the dictionary, we can immediately look in another direction.
This algorithm is given by the following pseudocode:

If a character
sequence is not a
prefix of any word
in the dictionary, we
can terminate
searching in that
direction.

for each row R
for each column C
for each direction D
for each word length L
check if L chars starting at row R column
C in direction D form a word
if they do not form a prefix,
break; // the innermost loop

The only remaining algorithmic detail is the implementation of the prefix
test: Assuming that the current character sequence is not in the word list, how can
we decide whether it is a prefix of some word in the word list? The answer turns
out to be simple. Recall from Section 6.4.3 that the binarySearch method in the
Collections API returns either the index of a match or the position of the smallest
element that is at least as large as the target (as a negative number). The caller
can easily check on whether a match is found. If a match is not found, verifying
that the character sequence is a prefix of some word in the list also is easy,
because, if it is, it must be a prefix of the word in the position implied in the
return value (in Exercise 10.3 you are asked to prove this outcome).

Prefix testing can
also be done by
binary search.

10.1.2 java implementation

Our implementa-
tion follows the
algorithm
description.

Our Java implementation follows the algorithm description almost verbatim.
We design a WordSearch class to store the grid and word list, as well as the corre-
sponding input streams. The class skeleton is shown in Figure 10.2. The public