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)
 */