 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/imperative-programming/4/a/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 4 / a / Solution by

Codex  0 2026-10-31

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 . l e n g t h

. 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 . l e n g t h - i

. At exit,

co n t ain s (w) ⟺ the full path exists and its terminal flag is true .

(1)

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.

 Read the full article

 New to topics? Read the docs here!