= Solution
Traverse the <trie> along the input <string>, stopping as soon as the required child is absent. All words and letter collections in this question are assumed to use only lowercase letters `a` through `z`; this is the alphabet represented by the given child <array>. Put the following methods inside the supplied `Trie` class.
``
def contains(w: String): Boolean = {
var t: Trie = this
var i = 0
while (i < w.length && t != null) {
t = t.children(toIndex(w.charAt(i)))
i += 1
}
t != null && t.complete
}
``
The <loop invariant> is that `t` is the <trie> node reached by the prefix `w.take(i)`, or null if that prefix has no path, with $0\leq i\leq w.length$. If `t` is null, no extension can be a stored word. Otherwise, following the next character preserves the <loop invariant>. The <loop variant> is $w.length-i$. At exit,
$$
\boxed{contains(w)\iff\text{the full path exists and its terminal flag is true}.}
$$
A prefix that exists but is not complete must return false. The empty <string> is present exactly when the root's `complete` flag is true. The <time complexity> is $O(1+|w|)$, with constant <auxiliary space>.
Back to article page
