0208-implement-trie-prefix-tree.scala

importscala.collection.mutable.HashMap

classTrie() {
classTrieNode {
valchildren:HashMap[Char, TrieNode] =HashMap()
varisEndOfWord=false
 }

privatevarroot:TrieNode=newTrieNode()

definsert(word: String):Unit= {
varcurr= root
 word.foreach(c => {
if (!curr.children.contains(c)) {
 curr.children(c) =newTrieNode() 
 }

 curr = curr.children(c)
 })

 curr.isEndOfWord =true
 }

defsearch(word: String):Boolean= {
 traverse(word) match {
caseSome(endNode) => endNode.isEndOfWord
caseNone=>false
 }
 }

defstartsWith(prefix: String):Boolean= {
 traverse(prefix).isDefined
 }

privatedeftraverse(word: String):Option[TrieNode] = {
varcurr= root
for (c <- word) {
if (!curr.children.contains(c)) {
returnNone
 } else {
 curr = curr.children(c) 
 }
 }

returnSome(curr)
 }
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
*/