= Solution
Create only the missing nodes along the required <trie> path, and mark its last node complete.
``
def add(w: String): Unit = {
var t: Trie = this
var i = 0
while (i < w.length) {
val k = toIndex(w.charAt(i))
if (t.children(k) == null) t.children(k) = new Trie
t = t.children(k)
i += 1
}
t.complete = true
}
``
The <loop invariant> is that the path for `w.take(i)` exists and ends at `t`, while the <set> of complete words remains unchanged from entry. A fresh node has all children null and `complete == false`, so creating an unfinished path introduces no stored word. The <loop variant> is $w.length-i$. At termination the full path exists; setting its final flag gives
$$
\boxed{D_{\mathrm{after}}=D_{\mathrm{before}}\cup\{w\}.}
$$
Existing paths and terminal flags are untouched, so adding an existing word is idempotent. Adding the empty <string> marks the root. The <time complexity> is $O(1+|w|)$ because the alphabet size is fixed; at most $|w|$ new <trie> nodes are allocated.
Back to article page
