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

CHAPTER 10. SEARCHING
78
the reader has already seen such an algorithm in §3.
Searching algorithms and their efficiency largely depends on the underlying
data structure being used to store the data. For instance it is quicker to deter-
mine whether an item is in a hash table than it is an array, similarly it is quicker
to search a BST than it is a linked list. If you are going to search for data fairly
often then we strongly advise that you sit down and research the data structures
available to you. In most cases using a list or any other primarily linear data
structure is down to lack of knowledge. Model your data and then research the
data structures that best fit your scenario.

---

Chapter 11
Strings
Strings have their own chapter in this text purely because string operations
and transformations are incredibly frequent within programs. The algorithms
presented are based on problems the authors have come across previously, or
were formulated to satisfy curiosity.
11.1
Reversing the order of words in a sentence
Defining algorithms for primitive string operations is simple, e.g. extracting a
sub-string of a string, however some algorithms that require more inventiveness
can be a little more tricky.
The algorithm presented here does not simply reverse the characters in a
string, rather it reverses the order of words within a string. This algorithm
works on the principal that words are all delimited by white space, and using a
few markers to define where words start and end we can easily reverse them.
79

---

CHAPTER 11. STRINGS
80
1) algorithm ReverseWords(value)
2)
Pre:
value 6= ∅, sb is a string buffer
3)
Post: the words in value have been reversed
4)
last ← value.Length − 1
5)
start ← last
6)
while last ≥ 0
7)
// skip whitespace
8)
while start ≥ 0 and value[start] = whitespace
9)
start ← start − 1
10)
end while
11)
last ← start
12)
// march down to the index before the beginning of the word
13)
while start ≥ 0 and start 6= whitespace
14)
start ← start − 1
15)
end while
16)
// append chars from start + 1 to length + 1 to string buffer sb
17)
for i ← start + 1 to last
18)
sb.Append(value[i])
19)
end for
20)
// if this isn’t the last word in the string add some whitespace after the word in the buffer
21)
if start > 0
22)
sb.Append(‘ ’)
23)
end if
24)
last ← start − 1
25)
start ← last
26)
end while
27)
// check if we have added one too many whitespace to sb
28)
if sb[sb.Length −1] = whitespace
29)
// cut the whitespace
30)
sb.Length ← sb.Length −1
31)
end if
32)
return sb
33) end ReverseWords
11.2
Detecting a palindrome
Although not a frequent algorithm that will be applied in real-life scenarios
detecting a palindrome is a fun, and as it turns out pretty trivial algorithm to
design.
The algorithm that we present has a O(n) run time complexity. Our algo-
rithm uses two pointers at opposite ends of string we are checking is a palindrome
or not. These pointers march in towards each other always checking that each
character they point to is the same with respect to value. Figure 11.1 shows the