辞書の木について知りたいですか？

辞書木構造

多かれ少なかれ、楽しい特徴は上の図にあります。

まず、ルート・ノードには文字が含まれず、ルート・ノード以外のすべての子ノードには文字が含まれます。

第2：ルート・ノードから特定のノードまで、パス上を通過する文字をつなぎ合わせて、そのノードに対応する文字列を作ります。

第三に、各単語の共通接頭辞は文字ノードとして保持されます。

Trieキーワード検索プロセス：

1. 毎回ルート・ノードから検索を開始します；
2. キーワードの最初の文字を取得し、その文字に従って対応する子ノードを選択し、その子ノードに移動して検索を続行します；
3. 対応するサブノードでは、キーワードの2番目の文字が取得され、さらに対応するサブノードが検索のために選択されます；
4. その繰り返しです；
5. キーワードの文字がすべて取り出されたノードでは、そのノードに付随する情報が読み込まれ、検索が完了します。

Trie

• 文字列検索：既知の文字列に関する情報をTrieに保存し、未知の文字列が出現したかどうか、または出現した頻度を検索します。
• 文字列の最長の共通接頭辞：Trieは、複数の文字列の共通接頭辞を使用してストレージスペースを節約します。逆に、Trieに多数の文字列を保存する場合、特定の文字列の共通接頭辞をすばやく取得できます。
• ソート：トライ木は多項木であり、最初の順序が木全体を横断する限り、対応する出力文字列は辞書の順序でソートした結果です。
• 他のデータ構造やアルゴリズムの補助構造として：接尾辞木、ACオートマトンなど。

コード

leetcode p14 最長公開接頭辞辞書ツリーソリューション

class Solution {
 public String longestCommonPrefix(String[] strs) {
		if(strs == null || strs.length == 0) {
			return "";
		}
		TrieNode root = new TrieNode();
		for (String str : strs) {
			if(str == null || str.length() == 0) {
				return "";
			}
			add(root,str);
		}
		TrieNode cur = root;
		StringBuilder sb = new StringBuilder();
		while (cur.children.keySet().size() == 1 && !cur.isEnd) {
			Character character = cur.children.keySet().iterator().next();
			sb.append(character);
			cur = cur.children.get(character);
		}
		return sb.toString();
	}
	public void add(TrieNode root, String s) {
		char[] chars = s.toCharArray();
		TrieNode cur = root;
		for(int i = 0;i < chars.length; i++) {
			if(!cur.children.containsKey(chars[i])) {
				cur.children.put(chars[i],new TrieNode());
			}
			cur = cur.children.get(chars[i]);
		}
		cur.isEnd = true;
	}
	class TrieNode {
		boolean isEnd;
		HashMap<Character,TrieNode> children = new HashMap<>();
	}
}