MutableTrieNode

MutableTrie.scala

import scala.annotation.tailrec
import scala.collection.mutable

case class MutableTrieNode(h: mutable.HashMap[Char, MutableTrieNode], isWord: Boolean = false)
object MutableTrieNode {
  def empty = MutableTrieNode(mutable.HashMap.empty)

  def buildTrieNode(s: List[Char], t: MutableTrieNode = MutableTrieNode.empty): MutableTrieNode = {
    s match {
      case Nil => t.copy(isWord = true)
      case ::(head, next) =>
        t.h.get(head) match {
          case Some(value) =>
            t.h.update(head, buildTrieNode(next, value))
            t
          case None =>
            t.h.update(head, buildTrieNode(next))
            t
        }
    }
  }

  @tailrec
  def search(l: List[Char], t: MutableTrieNode,
             isPrefix: Boolean = false): Boolean = {
    l match {
      case head :: Nil =>
        t.h.get(head) match {
          case Some(value) if value.isWord || isPrefix =>
            search(Nil, value, isPrefix)
          case _ =>
            false
        }
      case ::(head, next) =>
        t.h.get(head) match {
          case Some(value) =>
            search(next, value, isPrefix)
          case None =>
            false
        }
      case Nil => true
    }
  }


  def constructFromListOfString(l: List[String],
                                t: MutableTrieNode = MutableTrieNode.empty): MutableTrieNode = {
    def cHelper(l: List[String], trie: MutableTrieNode): MutableTrieNode = {
      l.foldLeft(trie)((a,b) => buildTrieNode(b.toList, a))
    }
    cHelper(l, t)
  }
}


MutableTrieNode.constructFromListOfString(List("tea"))
MutableTrieNode.search("ten".toList, MutableTrieNode.constructFromListOfString(List("tea", "ted", "tennis")), isPrefix = true)