ArrayLists - Building Java Programs: A Back to Basics Approach - page 662

couple of words in a row in both lists that don't match, followed by matches with the
words " the " , " through " , and " town. " , and a final unique word in each list. The
complete set of matches is as follows:
list1 = [all, and, bus, go, on, round, round., the, through, town., wheels]
list2 = [all, bus, go, on, swish,, swish., the, through, town., wipers]
We want to design an algorithm that parallels what people do when they look for
matches. Imagine putting a finger from your left hand on the first list and putting a
finger from your right hand on the second list to keep track of where you are in each
list. We will compare the words at which you are pointing and, depending on how
they compare, move one or both fingers forward.
We start with the left finger on the word " all " in the first list and the right finger
on the word " all " in the second list.
list1 = [all, and, bus, go, on, round, round., the, through, town., wheels]
list2 = [all, bus, go, on, swish,, swish., the, through, town., wipers]
The words match, so we add that word to the overlap and move both fingers forward:
list1 = [all, and, bus, go, on, round, round., the, through, town., wheels]
list2 = [all, bus, go, on, swish,, swish., the, through, town., wipers]
Now we are pointing at the word " and " from the first list and the word " bus "
from the second list. The words don't match. So what do you do? It turns out that the
word " bus " in list2 is going to match a word in list1 . So how do you know to
move the left finger forward? Because the lists are sorted and because the word
" and " comes before the word " bus " , we know that there can't be a match for the
word " and " in the second list. Every word that comes after " bus " in the second list
will be alphabetically greater than " bus " , so the word " and " can't be there. Thus, we
can move the left finger forward to skip the word " and " :
list1 = [all, and, bus, go, on, round, round., the, through, town., wheels]
list2 = [all, bus, go, on, swish,, swish., the, through, town., wipers]