This chapter will cover more advanced string algorithms than the previous chapters have discussed. They should be easier to understand now that you have learned about some other data structures. Specifically, this chapter will focus on string searching algorithms.
Trie (Prefix Tree)
is special type of tree used commonly for searching strings and matching on stored strings. At each level, nodes can branch off to form complete words
. For example, Figure 18-1
shows a trie of the words: Sammie
. Each ending node has a boolean flag: isCompleted
. This indicates ...