Trie

ImmutableTrie.scala

import scala.annotation.tailrec
import scala.collection.immutable.HashMap

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

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

  @tailrec
  def search(l: List[Char], t: TrieNode,
             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 _ =>
            println(head)
            false
        }
      case ::(head, next) =>
        t.h.get(head) match {
          case Some(value) =>
            println(value)
            search(next, value, isPrefix)
          case None =>
            false
        }
      case Nil => true
    }
  }


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


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