AnAutocompleteExample.scala

import scala.annotation.tailrec

object Main {

    // https://www.byte-by-byte.com/autocomplete/
    
    type Words = collection.mutable.Set[String]
    val Words = collection.mutable.Set
    type Index = collection.mutable.HashMap[String, Node]
    val Index = collection.mutable.HashMap
    type ResultSet = collection.mutable.ListBuffer[String]
    val ResultSet = collection.mutable.ListBuffer

    case class Node(prefix: String, words : Words = Words.empty, nodes : Index = Index.empty)

    @inline final def getPrefix(s: String, till: Int) = s.substring(0, till)
    @inline final def atLastChar(s: String, till: Int) = s.length <= till

    @tailrec def insert(node: Node, s: String, till: Int): Unit = {
        if (atLastChar(s, till))
            node.words.add(s)
        else {
            val prefix = getPrefix(s, till)
            if (!node.nodes.contains(prefix)) node.nodes(prefix) = Node(prefix)
            insert(node.nodes(prefix), s, till + 1)
        }
    }

    @tailrec def gotoNode(node: Node, pattern: String, till: Int): Option[Node] = {
        if (node.prefix == pattern) Some(node)
        else {
            val prefix = getPrefix(pattern, till)
            if (node.nodes.contains(prefix)) gotoNode(node.nodes(prefix), pattern, till + 1)
            else Some(node)
        }
    }

    def collectWords(node: Node, pattern: String, resultSet: ResultSet): Unit = {
        node.words.foreach { i => if (i.startsWith(pattern)) resultSet.append(i) }
        node.nodes.foreach { kv => if (kv._1.startsWith(pattern)) collectWords(kv._2, pattern, resultSet) }
    }

    def collectPrefixes(node: Node, pattern: String) : ResultSet = {
        val rsl = gotoNode(node, pattern, 1)
        rsl match {
            case None =>
                ResultSet.empty
            case Some(n) =>
                val resultSet: ResultSet = ResultSet.empty
                collectWords(n, pattern, resultSet)
                resultSet
        }
    }

    def main(args: Array[String]): Unit = {

        val words = Array("abc", "acd", "bcd", "def", "a", "aba")
        val node = Node("")
        words.foreach { i => insert(node, i, 1) }

        println(node)
        println(collectPrefixes(node, ""))
        println(collectPrefixes(node, "a"))
        println(collectPrefixes(node, "def"))
        println(collectPrefixes(node, "abcd"))
        println(collectPrefixes(node, "abc"))
        println(collectPrefixes(node, "b"))
    }
}