抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

37 | 面试题:实现一个字典树

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
}

}

0条评论

发表评论