D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

§11.1. This simply removes any punctuation
from a word. The reason we perform this operation on each word is so that
we can build a more accurate unique string collection, e.g. “test”, and “test!”
are the same word minus the punctuation. Figure 11.4 shows the undesired and
desired sets for the unique set respectively.
11.5
Determining the first matching character
between two strings
The algorithm to determine whether any character of a string matches any of the
characters in another string is pretty trivial. Put simply, we can parse the strings
considered using a double loop and check, discarding punctuation, the equality
between any characters thus returning a non-negative index that represents the
location of the first character in the match (Figure 11.5); otherwise we return
-1 if no match occurs. This approach exhibit a run time complexity of O(n
2
).

---

CHAPTER 11. STRINGS
85
t
s
e
t
0
1
2
3
4
s
r
e
t
p
0
1
2
3
4
5
6
Word
Match
i
t
s
e
t
0
1
2
3
4
s
r
e
t
p
0
1
2
3
4
5
6
i
index
t
s
e
t
0
1
2
3
4
s
r
e
t
p
0
1
2
3
4
5
6
i
index
index
a)
b)
c)
Figure 11.5: a) First Step; b) Second Step c) Match Occurred
1) algorithm Any(word,match)
2)
Pre: word, match 6= ∅
3)
Post: index representing match location if occured, −1 otherwise
4)
for i ← 0 to word.Length − 1
5)
while word[i] = whitespace
6)
i ← i + 1
7)
end while
8)
for index ← 0 to match.Length − 1
9)
while match[index] = whitespace
10)
index ← index + 1
11)
end while
12)
if match[index] = word[i]
13)
return index
14)
end if
15)
end for
16)
end for
17)
return −1
18) end Any
11.6
Summary
We hope that the reader has seen how fun algorithms on string data types
are. Strings are probably the most common data type (and data structure -
remember we are dealing with an array) that you will work with so its important
that you learn to be creative with them. We for one find strings fascinating. A
simple Google search on string nuances between languages and encodings will
provide you with a great number of problems. Now that we have spurred you
along a little with our introductory algorithms you can devise some of your own.

---

Appendix A
Algorithm Walkthrough
Learning how to design good algorithms can be assisted greatly by using a
structured approach to tracing its behaviour. In most cases tracing an algorithm
only requires a single table. In most cases tracing is not enough, you will also
want to use a diagram of the data structure your algorithm operates on. This
diagram will be used to visualise the problem more effectively. Seeing things
visually can help you understand the problem quicker, and better.
The trace table will store information about the variables used in your algo-
rithm. The values within this table are constantly updated when the algorithm
mutates them. Such an approach allows you to attain a history of the various
values each variable has held. You may also be able to infer patterns from the
values each variable has contained so that you can make your algorithm more
efficient.
We have found this approach both simple, and powerful. By combining a
visual representation of the problem as well as having a history of past values
generated by the algorithm it can make understanding, and solving problems
much easier.
In this chapter we will show you how to work through both iterative, and
recursive algorithms using the technique outlined.
A.1
Iterative algorithms
We will trace the IsPalindrome algorithm (defined in §11.2) as our example
iterative walkthrough. Before we even look at the variables the algorithm uses,
first we will look at the actual data structure the algorithm operates on. It
should be pretty obvious that we are operating on a string, but how is this
represented? A string is essentially a block of contiguous memory that consists
of some char data types, one after the other. Each character in the string can
be accessed via an index much like you would do when accessing items within
an array. The picture should be presenting itself - a string can be thought of as
an array of characters.
For our example we will use IsPalindrome to operate on the string “Never
odd or even” Now we know how the string data structure is represented, and
the value of the string we will operate on let’s go ahead and draw it as shown
in Figure A.1.
86

---