Kotlin Coding Test Course, Try

1. What is a Trie?

A Trie is a tree data structure used for multi-prefix string searching.
Each node represents the path for each character of the string, and the path from root to leaf forms
a single string. Therefore, using a Trie allows sharing common parts of strings, resulting in high
memory efficiency.

For example, when we have words like “cat”, “cab”, “dog”, these words can be stored in a Trie as follows:

                (root)
                ├── c
                │   ├── a
                │   │   ├── b
                │   │   └── t
                │   └── d
                └── d
                    └── o
                        └── g
            

Thus, Tries are a powerful tool for efficient storage and retrieval of a set of strings.
They are particularly effective for prefix searching, word completion, and lexicographical ordering problems.

2. Implementation of the Trie Data Structure

To implement a Trie, we will define two main classes:
TrieNode and Trie.

                class TrieNode {
                    val children: MutableMap = mutableMapOf()
                    var isEndOfWord: Boolean = false
                }
                
                class Trie {
                    private val root: TrieNode = TrieNode()
                    
                    fun insert(word: String) {
                        var node = root
                        for (char in word) {
                            node = node.children.getOrPut(char) { TrieNode() }
                        }
                        node.isEndOfWord = true
                    }
                    
                    fun search(word: String): Boolean {
                        var node = root
                        for (char in word) {
                            node = node.children[char] ?: return false
                        }
                        return node.isEndOfWord
                    }
                }
            

The code above provides the basic insert and search functionality of a Trie. The TrieNode
class contains a collection of child nodes and a flag indicating the end of a word.
The Trie class provides insert and search functions, using the getOrPut function to
dynamically create child nodes.

3. Problem Description: Word Search

Problem: Given a list of words and a list of queries, write a program to check whether
each query is included in the word list. Specifically, it should be able to efficiently search for words
that share common prefixes.

Input:
– Word List: [“apple”, “app”, “bat”, “ball”, “batman”]
– Query List: [“app”, “bat”, “banana”, “appl”, “ball”]

Output: Return a list indicating whether each query exists in the word list,
represented as Boolean values. For example, [true, true, false, false, true] should be output.

4. Problem Solving Process

To solve the problem, we will first insert the word list into the Trie,
and then check each query by searching in the Trie.

                fun wordSearch(words: List, queries: List): List {
                    val trie = Trie()
                    for (word in words) {
                        trie.insert(word)
                    }
                    return queries.map { trie.search(it) }
                }
            

The wordSearch function first creates a Trie object and
inserts words into the Trie using the provided word list.
It then iterates through the query list and calls the search method to
check whether each query exists.

5. Code Execution Example

                fun main() {
                    val words = listOf("apple", "app", "bat", "ball", "batman")
                    val queries = listOf("app", "bat", "banana", "appl", "ball")
                    val result = wordSearch(words, queries)
                    println(result) // [true, true, false, false, true]
                }
            

Running the above code block will output a list containing Boolean values
that represent answers for the queries. In this way, Tries
simplify and efficiently solve string search problems.

6. Utility and Extension of Tries

Tries can be applied to several other problems besides string searching.
For example, autocomplete features and prefix searching are
some of the most common use cases for Tries. Additionally,
you can extend the Trie to incorporate additional functionalities.
You can implement a feature to find all words starting with a
specific prefix or find words that start with specific patterns.

For instance, you could add a startsWith method to find all words starting with a specific prefix as follows.

                fun startsWith(prefix: String): Boolean {
                    var node = root
                    for (char in prefix) {
                        node = node.children[char] ?: return false
                    }
                    return true
                }
            

This method checks whether the given prefix exists in the Trie.
Such extension functionalities are particularly useful when processing large
datasets.

7. Conclusion

In this lesson, we have implemented a Trie using Kotlin and explored the process of
solving string search problems. Tries are a very useful data structure for
managing and searching strings efficiently, and they frequently appear in
coding tests. By attempting various approaches to solve problems and
utilizing Tries appropriately, you will be able to solve a wide range of
algorithmic problems with ease.

In the next lesson, we will cover variations of Tries and other advanced string algorithms.
Please continue to build your skills through more practice problems and actual coding test problems.
Thank you!