Utilities - Data Structures and Problem Solving Using Java - page 505

return list will have size k ), and provide the running time of your
routine.

Many companies like to have phone numbers that can be spelled on
the phone pad, rather than being random digits. For instance, 1-800-
DRWEISS is actually 1-800-379-3477. Also, numbers, such as
account numbers can sometimes be more easily remembered when
they can be spelled out on a phone pad. For instance, the account
number 7378378377, which is hard to remember would be easier to
remember if one observes that the word "REQUESTERS" types the
same sequence of buttons on a phone pad. This account number is
special, because "PERVERTERS" also types the same sequence.
Assume that you have a file containing one word per line. Write a
program that finds the account numbers that contain the MOST
matching words in the file. If there are several such account numbers,
print each of them out, along with the words that they match.

12.25

Suppose you have an array consisting exclusively of five letter
words. Two words are transformable to each other if they are identi-
cal in every position except one. Thus, “blood” and “blond” are
transformable. “blood” and “flood” are also transformable. Write a
method that takes as parameter an array of String containing only
five letter words and outputs the word that is transformable to the
most other words. In case of a tie, you should output all such words.
Your algorithm must run in sub-quadratic time, so you cannot simply
compare each pair of words.
Hint : Create five separate maps, with map i grouping together
words that are identical except for position i . Use those maps to
create a sixth map that tells you all the words than any word is
transformable to.

12.26

A MultiSet , as described in Exercise 6.32 is like a Set , but allows
duplicates. Exercise 6.32 suggested an implementation that uses a
Map , in which the value represents a count of the number of duplicates.
However, that implementation loses information. For instance if we
add a BigDecimal representing 4.0 and another BigDecimal representing
4.000 (note that for these two objects, compareTo yields 0, but equals
yields false), the first occurrence will be inserted with a count of 2,
and toString will necessarily lose information about 4.000 being in
the multiset. Consequently, an alternative implementation would be
to use a Map , in which the value represents a list of all additional
instances of the key. Write a complete implementation of the MultiSet ,
and test it by adding several logically equal BigDecimals .

12.27