insertsearchstartsWithメソッドを使用してトライを実装します。

例:

Trie trie = new Trie();trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app"); 
trie.search("app"); // returns true

注:

• すべての入力は小文字で構成されていると仮定することができますa-z。
• すべての入力は空でない文字列であることが保証されています。

これはleetcodeの問題です：

解決策：

この問題の解決に飛び込む前に、まずTrieデータ構造が簡単に理解されます。

トライは、主に文字列を格納するために使用される順序付けられたツリー構造です。 文字列を格納するために使用される理由は、検索時間が速いためです。 トライで文字列を見つける複雑さはO（m）で、mは文字列の長さです。 Trieに100万個の文字列を格納していて、特定の文字列を見つける必要がある場合は、catとしましょう。

trieという用語は、文字列のコレクションからの文字列の取得を非常に簡単にするため、retrievalという単語から来ました。 トリエは接頭木とも呼ばれます。

Trieではルートは空であり、各子ノードには一つの文字だけが含まれています。 したがって、特定のノードが持つことができる子ノードの数は、特定の言語のアルファベットの数に依存します。 英語の単語を格納するためにトライを使用していると仮定すると、各ノードには26個の子ノードがあります。div>

上記の画像では、5つの子ノードのみが表示されていますしかし、実際のルートには26個の子ノードがあり、各アルファベットに1つずつあります。ここで、trieデータ構造でいくつかの文字列を表現する必要があるかどうかを見てみましょう。 Trieでball、bald、car、cat、dogを表す必要があるとします。 これは以下のようになります。 下の画像では、オレンジ色のノードは単語の終わりを意味します。div>

2 ここで、配列のインデックスは2になります。 あなたが気づいていない場合は、char-‘a’を実行して配列内の任意のアルファベットのインデックスを見つけます。 これを行うことによって、aのインデックスは0、bは1、cは2などです。 配列のインデックス2に移動し、新しいノードを割り当てます。

3。 今、私たちは第二のノードに私たちのポインタを移動します。 したがって、インデックス0を新しいノードに初期化します。p>

4。 ポインタを次のノードに移動します。 Catの次のアルファベットはtです。tのインデックスは19です。 インデックス19を新しいノードに初期化します。

5. 次のノードに移動します。 今、これ以上のアルファベットが挿入されるように残されていません。 そこで、このノードをendとしてマークします。/div>は、insertメソッドのjavaコードです。p>

public void insert(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
tempNode.child = new TrieNode();
}
tempNode = tempNode.child;
}
tempNode.isEnd = true;
}

以下は、searchとstartsWithメソッドを使用したこのプログラムの完全なJavaソリューションです。p>

class Trie {
class TrieNode {
static final int ALPHABET_SIZE = 26;
TrieNode child = new TrieNode; boolean isEnd;
}
TrieNode root;
/**
* Initialize your data structure here.
*/
public Trie() {
root = new TrieNode();
}
/**
* Inserts a word into the trie.
*/
public void insert(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
tempNode.child = new TrieNode();
}
tempNode = tempNode.child;
}
tempNode.isEnd = true;
}
/**
* Returns if the word is in the trie.
*/
public boolean search(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
return false;
}
tempNode = tempNode.child;
}
if (tempNode != null && tempNode.isEnd == false) {
return false;
}
return true;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String str) {
char data = str.toCharArray();
TrieNode tempNode = root;
for (char c : data) {
int index = c - 'a';
if (tempNode.child == null) {
return false;
}
tempNode = tempNode.child;
}
return true;
}
}