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 The loop invariant is that
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
}t is the trie node reached by the prefix w.take(i), or null if that prefix has no path, with . If t is null, no extension can be a stored word. Otherwise, following the next character preserves the loop invariant. The loop variant is . At exit,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 , with constant auxiliary space.Create only the missing nodes along the required trie path, and mark its last node complete.The loop invariant is that the path for
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
}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 . At termination the full path exists; setting its final flag givesExisting paths and terminal flags are untouched, so adding an existing word is idempotent. Adding the empty string marks the root. The time complexity is because the alphabet size is fixed; at most new trie nodes are allocated.Use trie search with a letter multiset. Counts avoid generating the same result repeatedly when the input contains equal letters. The backtracking explores a letter value once, irrespective of how many indistinguishable copies remain.At entry to
def allWords(ls: String): List[String] = {
val left = new Array[Int](26)
var i = 0
while (i < ls.length) {
left(toIndex(ls.charAt(i))) += 1
i += 1
}
var out = List.empty[String]
def visit(t: Trie, prefix: String): Unit = {
if (t.complete) out = prefix :: out
var k = 0
while (k < 26) {
val child = t.children(k)
if (left(k) > 0 && child != null) {
left(k) -= 1
visit(child, prefix + toChar(k))
left(k) += 1
}
k += 1
}
}
visit(this, "")
out.reverse
}visit, t is reached by prefix, and left(k) is the input multiplicity of letter minus its multiplicity in prefix. All these counts are nonnegative. Each recursive call consumes one available letter, and restoration makes sibling calls see the same counts as before that child. The recursion therefore terminates at depth at most , even when the dictionary contains longer words.A completed prefix is emitted once, and the traversal continues so that longer words with the same prefix are also found. Every emitted word is in the dictionary and uses at most the available multiplicities. Conversely, every dictionary word meeting those bounds has an existing trie path whose next letter has positive remaining count at every step; the traversal reaches its terminal node. A trie has a unique root path for each word, and each child is visited at most once per reached node. ThereforeThe boxed expression specifies the set of entries in the returned list, rather than its ordering. If the dictionary includes the empty string, the method includes it once. Counting costs ; visiting reachable nodes costs apart from string copying and output construction. The presented immutable-prefix construction additionally costs the sum of the prefix lengths it constructs. The recursion depth is at most , and the letter-count array has fixed size.
Articles by others on the same topic
There are currently no matching articles.