Trie查詢每個條目的時間復(fù)雜度，和字典中一共有多少條無關(guān)。

時間復(fù)雜度為O（W）

w為查詢單詞的長度

?

import java.util.TreeMap;public class Trie {private class Node {public boolean isWord;public TreeMap<Character, Node> next;public Node(boolean isWord) {this.isWord = isWord;next = new TreeMap<>();}public Node() {this(false);}}private Node root;private int size;public Trie() {root = new Node();size = 0;}// 返回Trie中存儲的單詞數(shù)量public int getSize() {return size;}// 向Trie中添加一個新的單詞wordpublic void add(String word) {Node cur = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);if (cur.next.get(c) == null)cur.next.put(c, new Node());cur = cur.next.get(c);}if (!cur.isWord) {cur.isWord = true;size++;}}//查詢單詞word是否在Trie中public boolean contains(String word){Node cur=root;for (int i = 0; i < word.length(); i++) {char c=word.charAt(i);if(cur.next.get(c)==null)return false;cur=cur.next.get(c);}return cur.isWord;} //查詢是否在Trie中有單詞以prefix為前綴public boolean isPrefix(String prefix) {Node cur=root;for (int i = 0; i < prefix.length(); i++) {char c=prefix.charAt(i);if(cur.next.get(c)==null)return false;cur=cur.next.get(c);}return true;} }

測試：

public class Main {public static void Main(String[] args){System.out.println("Pride and Prejudice");ArrayList<String> words=new ArrayList<>();if(FileOperation.readFile("pride-and-prejudice.txt", words)){long startTime = System.nanoTime();BSTSet<String> set=new BSTSet<String>();for(String word:words)set.add(word);for(String word:words)set.contains(word);long endTime = System.nanoTime();double time = (endTime - startTime) / 1000000000.0;System.out.println("Total different words: " + set.getSize());System.out.println("BSTSet: " + time + " s");startTime = System.nanoTime();Trie trie = new Trie();for(String word: words)trie.add(word);for(String word: words)trie.contains(word);endTime = System.nanoTime();time = (endTime - startTime) / 1000000000.0;System.out.println("Total different words: " + trie.getSize());System.out.println("Trie: " + time + " s");}} }

　　search可以搜索文字或正則表達式字符串，字符串只包含字母.或者a-z.

import java.util.TreeMap;public class WordDictionary {public class Node{private boolean isWord;public TreeMap<Character, Node> next;public Node(boolean isWord){this.isWord=isWord;next=new TreeMap<>();}public Node() {this(false);}}private Node root; public WordDictionary(){root =new Node();}public void addWord(String word) {Node cur = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);if (cur.next.get(c) == null)cur.next.put(c, new Node());cur = cur.next.get(c);}cur.isWord = true;}public boolean search(String word){return match(root, word, 0);}private boolean match(Node node,String word,int index) {if(index==word.length()) return node.isWord;char c=word.charAt(index);if(c!='.'){if(node.next.get(c)==null)return false;return match(node.next.get(c), word, index+1);}else{for (char nextChar :node.next.keySet()) {if(match(node.next.get(nextChar), word, index+1))return true;}return false; }} }

　　Trie和映射

import java.util.TreeMap;public class MapSum {private class Node{public boolean isWord;public int value;public TreeMap<Character, Node> next;public Node(int value){this.value=value;next=new TreeMap<>();}public Node(){this(0);}}private Node root;public MapSum() {root=new Node();}public void insert(String word,int val){Node cur=root;for (int i = 0; i < word.length(); i++) {char c=word.charAt(i);if(cur.next.get(c)==null)cur.next.put(c,new Node());cur=cur.next.get(c);}cur.value=val;}public int sum(String prefix){Node cur=root;for (int i = 0; i < prefix.length(); i++) {char c=prefix.charAt(i);if(cur.next.get(c)==null)return 0;cur=cur.next.get(c);}return sum(cur); }private int sum(Node node){if(node.next.size()==0)return node.value;int res=node.value;for (char c:node.next.keySet()) res+=sum(node.next.get(c));return res;} }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/sunliyuan/p/10742774.html

總結(jié)

以上是生活随笔為你收集整理的Java Trie字典树，前缀树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。