[LeetCode] 208 Implement Trie (Prefix Tree)

Description

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:

Trie() Initializes the trie object.

void insert(String word) Inserts the string word into the trie.

boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"][], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); //return True
trie.search("app"); //return False
trie.startsWith("app");//return True
trie.insert("app");
trie.search("app"); //return True

Constraints:

1 <= word.length, prefix.length <= 2000

word and prefix consist only of lowercase English letters.

At most 3 * 10^4 calls in total will be made to insert , search , and startsWith .

に答える

基本ストライプ、挿入、検索、および接頭辞の検索の問題を生成します.
まず、trieとtrieに入るノードクラスを作成します.

トリプルノード

マッピング(Map)を作成して、

サブノードを記録します.

は、その単語の終了を表すisEndを作成する.

生成者-最初のノードが現れたときに、新しいサブノードを表す海西地図を作成します.

getChildren()を作成して、

の現在のノードのサブマッピングを返します.

の現在のノードの終了を表すsetEnd()を作成します.

isEnd()を作成して、

の現在のノードが終了したかどうかを返します.

三輪車

ノードを発表します.

生成者は、ルートノードを3ノードに変更する.

insert

路線図を持ってきてください.

単語を見るたびに1文字です.

今、単語を1つずつ見て、今の文字が自分の地図にあるかどうかを見てみましょう.
含まれる場合は、現在のノードをサブノードに変更します.
ない場合は、新しいノードを作成し、<現在のテキスト、新しいノード>をサブマッピングに挿入します.
サブマッピングを現在のノードのサブマッピングに変更します.
現在の文字が最後の文字の場合、ノードの末尾になります.setEnd()に設定します.

search

本のサブマッピングを取得します.

が現在の文字を含むかどうかを示すフラグを作成し、trueに設定します.

の新しいノードを作成します.

今、単語を1つずつ見て、今の文字がサブ図にあるかどうかを見てみましょう.
含まれる場合は、現在のノードをサブノードに変更します.
サブマッピングを現在のノードのサブマッピングに変更します.
ない場合はflagをfalseに変換し、for文から終了します.

flagはtrueであり,ノード終了時に見つかったといえる.
この結果を返します.

startsWith
-ルートのサブマッピングを取得します.
-現在の文字が含まれているかどうかを示すフラグを作成し、trueに設定します.
-新しいノードを作成します.
-現在の単語を1つずつ表示し、現在の文字がサブマッピングにあるかどうかを確認します.
含まれる場合は、現在のノードをサブノードに変更します.サブノードを現在のノードのサブノードに変更します.
ない場合はflagをfalseに変更し、for文を終了します.
-flag値を返します.
ここでは、前が同じであれば後は関係ないので、flagがtrueであれば見つかりますが、falseであれば対応する単語がなくsearchに似ていますが、少し違います.

コード#コード#

class Trie {
    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Map<Character, TrieNode> children = root.getChildren();
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            TrieNode node;
            if (children.containsKey(curLetter)) {
                node = children.get(curLetter);
            } else {
                node = new TrieNode();
                children.put(curLetter, node);
            }
            children = node.getChildren();
            if (i == word.length() - 1) {
                node.setEnd();
            }
        }
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Map<Character, TrieNode> children = root.getChildren();
        boolean flag = true;
        TrieNode node = null;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (children.containsKey(curLetter)) {
                node = children.get(curLetter);
                children = node.getChildren();
            } else {
                flag = false;
                break;
            }
        }
        return flag && node.isEnd();
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Map<Character, TrieNode> children = root.getChildren();
        boolean flag = true;
        TrieNode node;
        for(int i = 0; i < prefix.length(); i++) {
            char curLetter = prefix.charAt(i);
            if (children.containsKey(curLetter)) {
                node = children.get(curLetter);
                children = node.getChildren();
            } else {
                flag = false;
                break;
            }
        }
        return flag;
    }
}

class TrieNode {
    private Map<Character, TrieNode> children;
    private boolean isEnd;
    
    public TrieNode() {
        children = new HashMap<>();
    }
    
    public Map<Character, TrieNode> getChildren() {
        return this.children;
    }
    
    public void setEnd() {
        this.isEnd = true;
    }
    
    public boolean isEnd() {
        return this.isEnd;
    }
}

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