class Lexicon
Lexicon
class supports efficient lookup operations for words and prefixes.
This version of Lexicon
is implemented internally using a data structure called a prefix tree or trie (pronounced "try"), which allows for efficient prefix and word searching.
Some runtimes below are expressed in terms of "W" where W represents the length of the word being added.
Constructor | ||
O(1) | Initializes a new empty lexicon. | |
O(WN) | Initializes a new lexicon that reads words from the given file or input stream. | |
Methods | ||
O(W) | Returns true if word is contained in the lexicon. |
|
O(W) | Returns true if any words in the lexicon begin with prefix . |
|
O(1) | Returns the number of words contained in the lexicon. | |
Operators | ||
O(N) | Iterates through the words in a lexicon in alphabetical order. |
Lexicon(); Lexicon(string filename);
EnglishWords.dat
containing a list of words in English. The standard code pattern
to initialize that lexicon looks like this:
Lexicon english("EnglishWords.dat");
Usage:
Lexicon lex; Lexicon lex(filename);
bool contains(string word) const;
true
if word
is contained in the
lexicon. In the Lexicon
class, the case of letters is
ignored, so "Zoo" is the same as "ZOO" or "zoo".
Usage:
if (lex.contains(word)) ...
bool containsPrefix(string prefix) const;
prefix
.
Like containsWord
, this method ignores the case of letters
so that "MO" is a prefix of "monkey" or "Monday".
Usage:
if (lex.containsPrefix(prefix)) ...
int size() const;
Usage:
int n = lex.size();
for (string word : lex)
Usage:
for (string word : lex) { cout << word << endl; }