Daily LeetCode Challenge - 208. Implement Trie (Prefix Tree)

Problem From.
https://leetcode.com/problems/implement-trie-prefix-tree/

오늘 문제는 단어들과 그 단어들에 대한 처리가 적힌 array 가 주어졌을때, 각각의 결과를 반환하는 문제였다. 단어에 대한 처리는 단어를 사전에 추가하는 insert 와 단어를 찾는 search 그리고 단어의 앞이 일치하는지 확인하는 startsWith 가 있었다.

해당 작업들을 빠르게 처리하기 위해 trie 자료구조를 사용하였다. 이 자료구조는 String 에 대한 검색을 빠르게 처리하게 해주는 자료구조로 String 의 한 글자씩을 node 로 나누어 저장하고 있어서 검색속도를 빠르게 할 수 있다는 장점이 있었다.

insert 함수에서는 trieTree 에 각각의 단어를 저장하고 있는 path 를 만들고,
search 함수에서는 각각의 path 를 따라서 탐색할때 자식 노드가 비어있으면 false 를 반환하게 하였다.
startsWith 함수에서는 각각의 path 를 따라서 탐색하다가 중간까지 자식 노드가 비어있지 않으면 true 를 반환하도록 만들었다.

class Trie() {
    
    class TrieNode {
        val children = Array<TrieNode?>(26) { null }
        var isWord = false
    }

    val trieTree = TrieNode()

    fun insert(word: String) {
        var path = trieTree
        
        for(i in word) {
            val w = i - 'a'
            if(path.children[w] == null) path.children[w] = TrieNode()
            path = path.children[w]!!
        }
        path.isWord = true
    }

    fun search(word: String): Boolean {
        var path = trieTree
        
        for(i in word) {
            val w = i - 'a'
            if(path.children[w] == null) return false
            path = path.children[w]!!
        }
        return path.isWord
    }

    fun startsWith(prefix: String): Boolean {
        var path = trieTree
        
        for(i in prefix) {
            val w = i - 'a'
            if(path.children[w] == null) return false
            path = path.children[w]!!
        }
        return true
    }

}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */