208. 实现 Trie (前缀树)

这题的思路，是拆分字符，简单的做法就是每个字符都拆一拆。字典树的结构看上一篇文章。

class Trie() {

    /** Initialize your data structure here. */

    inner class TrieNode(var `val`: Char) {
        var children = arrayOfNulls<TrieNode>(52)
        var isEndOfWord = false
    }

    val root = TrieNode(' ')

    /** Inserts a word into the trie. */
    fun insert(word: String) {
        var ws = root
        word.toCharArray().forEach {
            if (ws.children[it - 'a'] == null) {
                ws.children[it - 'a'] = TrieNode(it)
            }
            ws = ws.children[it - 'a']!!
        }
        ws.isEndOfWord = true
    }

    /** Returns if the word is in the trie. */
    fun search(word: String): Boolean {
        var ws = root
        word.toCharArray().forEach {
            val node = ws.children[it - 'a']
            node ?: return false
            ws = node
        }
        return ws.isEndOfWord
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    fun startsWith(prefix: String): Boolean {
        var ws = root
        prefix.toCharArray().forEach {
            val node = ws.children[it - 'a']
            node ?: return false
            ws = node
        }
        return true
    }

}