LeetCode日本語修行1日目- [208- トライ木の実現]
早速、今日の日課を確認しましょう
208:トライ木の実現
参考:https://leetcode-cn.com/problems/implement-trie-prefix-tree
トライ木について
トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。
参考:https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)
問題の内容
以下のメソッドを実装
ー Trie() トライ木を初期化します。
ー void insert(String word) トライ木に文字列を挿入する word 。
ー boolean search(String word) 文字列wordがトライ木にある場合、trueに戻ります。す検索前に既に挿入されました。そうでなければfalseに戻ります。
ー boolean startsWith(String prefix) 前に挿入した文字列ワードのプレフィックスの一つがprefixである場合、trueに戻ります。そうでなければfalseに戻ります。
例:
入力
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
出力
[null, null, true, false, true, null, true]
説明
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
ヒント:
1<=word.lengthを選択します。prefix.length<=2000
ワードとprefixは小文字だけで構成されています。
insert、search、starts Withの呼び出し回数は合計3*104回を超えません。
さて、実装を始めましょう。
実際内容から見ると、文字列が含まれているかどうかを判断することですね。
ですが、普通に string.contains()を実現すると、本題から逸れる。
順序付き木を使って実装します
class Trie() {
class TrieNode{
var children = arrayOfNulls<TrieNode>(26)
var isEnd = false
fun containsKey(ch: Char): Boolean{
return children[ch - 'a'] != null
}
fun get(ch: Char): TrieNode? {
return children[ch - 'a']
}
fun put(ch: Char,node: TrieNode?){
children[ch - 'a'] = node
}
}
/** Initialize your data structure here. */
private var root: TrieNode = TrieNode()
/** Inserts a word into the trie. */
fun insert(word: String) {
var node: TrieNode? = root
for(c in word){
if(!node!!.containsKey(c)){
node.put(c,TrieNode())
}
node = node.get(c)
}
node!!.isEnd = true
}
private fun searchPrefix(word: String): TrieNode? {
var node: TrieNode? = root
for(c in word){
if(node!!.containsKey(c)){
node = node.get(c)
}else{
return null
}
}
return node
}
/** Returns if the word is in the trie. */
fun search(word: String): Boolean {
val node = searchPrefix(word)
return node != null && node.isEnd
}
/** Returns if there is any word in the trie that starts with the given prefix. */
fun startsWith(prefix: String): Boolean {
val node = searchPrefix(prefix)
return node != null
}
}
/**
* 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)
*/
Author And Source
この問題について(LeetCode日本語修行1日目- [208- トライ木の実現]), 我々は、より多くの情報をここで見つけました https://qiita.com/Aethey/items/9f2400d762bc16eac4da著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .