Phone dictionary using Trie in kotlin

To implement a phone dictionary using Trie, you would need to store a set of valid words in the Trie data structure, where each node represents a character in the words and edges connect parent nodes to their child nodes. Here’s an example implementation of a phone dictionary using Trie in Kotlin:

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var isWord = false
}
class PhoneDictionary {
    private val root = TrieNode()
    private val numberToLetters = mapOf(
        '2' to "abc",
        '3' to "def",
        '4' to "ghi",
        '5' to "jkl",
        '6' to "mno",
        '7' to "pqrs",
        '8' to "tuv",
        '9' to "wxyz"
    )
    fun insertWord(word: String) {
        var current = root
        for (c in word) {
            current.children.getOrPut(c) { TrieNode() }
            current = current.children[c]!!
        }
        current.isWord = true
    }
    fun searchWords(number: String): List<String> {
        val words = mutableListOf<String>()
        dfs(root, number, "", words)
        return words
    }
    private fun dfs(node: TrieNode, number: String, current: String, words: MutableList<String>) {
        if (number.isEmpty()) {
            if (node.isWord) words.add(current)
            return
        }
        for (c in numberToLetters[number.first()]!!) {
            val child = node.children[c] ?: continue
            dfs(child, number.substring(1), current + c, words)
        }
    }
}
fun main() {
    val dictionary = PhoneDictionary()
    dictionary.insertWord("apple")
    dictionary.insertWord("banana")
    dictionary.insertWord("orange")

    println(dictionary.searchWords("27753")) // [apple]
    println(dictionary.searchWords("226262")) // [banana]
    println(dictionary.searchWords("672643")) // [orange]
}

In this example, the TrieNode class represents a node in the Trie data structure, with a children map that maps each character to its child node and a isWord flag that indicates whether the current node represents the end of a word. The PhoneDictionary class provides methods for inserting words into the dictionary and searching for words that match a given phone number. The numberToLetters map maps each digit to its corresponding set of letters on a phone keypad.

Step Involved are :

1. Define the TrieNode class, which represents a node in the Trie data structure. Each TrieNode has a children map that maps each character to its child node, and a isWord flag that indicates whether the current node represents the end of a word.
2. Define the PhoneDictionary class, which contains the root node of the Trie data structure and a map that maps each digit to its corresponding set of letters on a phone keypad.
3. Implement the insertWord method of the PhoneDictionary class. This method takes a word as input and inserts it into the Trie by iterating over each character in the word and creating a new node for each character. For each character, the method checks if the character already exists as a child node of the current node. If not, it creates a new child node for the character and adds it to the children map. The final node of the word is marked with the isWord flag set to true.
4. Implement the searchWords method of the PhoneDictionary class. This method takes a phone number as input and returns a list of all words in the Trie that can be formed by combining the characters associated with the nodes along the path from the root node to a final node. The method performs a depth-first search (DFS) of the Trie starting from the root node and matching each digit in the phone number to its corresponding set of letters. For each letter in the set, the method recursively calls itself with the remaining digits of the phone number and the corresponding child node of the current node. If the child node is not null, the method appends the letter to the current string and continues the DFS. If the child node represents the end of a word, the word is added to the words list.
5. In the main function, create a new instance of the PhoneDictionary class and insert some words into the Trie using the insertWord method.
6. Call the searchWords method of the PhoneDictionary class with different phone numbers as input to test the Trie’s functionality. The method returns a list of all words in the Trie that can be formed by combining the characters associated with the nodes along the path from the root node to a final node that matches the phone number.

The resulting list of words is returned as the search result.

[apple]
[banana]
[orange]