Trie
关于Trie的几种实现方式
children node的存储
1可以用hashmap来存储children，HashMap<Character, TrieNode> children, 优势是利用contains函数便于查找
2用数组 TrieNode[] children; 通过index来查找，最多也就26个char(认为忽略大小写)
Search 函数：iterative 即可，可以将search和startwith合并
My solution ：HashMap + iterative
class TrieNode {// Initialize your data structure here.private char value;private boolean isend;// mark whether is end node//children of the nodepublic HashMap<Character, TrieNode> children;public TrieNode() {isend = false;children = new HashMap<Character, TrieNode>();}public TrieNode(char c){value = c;isend = false;children = new HashMap<Character, TrieNode>();}public boolean isEnd(){return isend;}public void setEnd(){isend = true;} }public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}// Inserts a word into the trie.public void insert(String word) {if(word == null || word.length() == 0) return;//bfs level insertTrieNode cur = root;for(int i = 0; i < word.length(); i++){char c = word.charAt(i);HashMap<Character, TrieNode> child = cur.children;if(child.containsKey(c)){//no need insertcur = child.get(c);}else{//insert a new trie nodeTrieNode newchild = new TrieNode(c);child.put(c, newchild);cur = newchild;}}//mark end cur.setEnd();}// Returns if the word is in the trie.public boolean search(String word) {if(word == null || word.length() == 0) return false;TrieNode cur = root;for(int i = 0; i < word.length(); i++){char c = word.charAt(i);HashMap<Character, TrieNode> child = cur.children;if(!child.containsKey(c)){//no char return false;}else{//continue searchcur = child.get(c);}}return cur.isEnd();}// Returns if there is any word in the trie// that starts with the given prefix.public boolean startsWith(String prefix) {if(prefix == null || prefix.length() == 0) return false;TrieNode cur = root;for(int i = 0; i < prefix.length(); i++){char c = prefix.charAt(i);HashMap<Character, TrieNode> child = cur.children;if(!child.containsKey(c)){//no char return false;}else{//continue searchcur = child.get(c);}}return true;}}// Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key"); View Code
其他解法
class TrieNode {// Initialize your data structure here.private char value;private boolean isend;// mark whether is end node//children of the nodepublic TrieNode[] children;public TrieNode() {isend = false;children = new TrieNode[26];}public TrieNode(char c){value = c;isend = false;children = new TrieNode[26];}public boolean isEnd(){return isend;}public void setEnd(){isend = true;} } public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}// Inserts a word into the trie.public void insert(String word) {if(word == null || word.length() == 0) return;//bfs level insertTrieNode cur = root;for(int i = 0; i < word.length(); i++){char c = word.charAt(i);int index = c - 'a';if(cur.children[index] == null){//insert a new nodecur.children[index] = new TrieNode(c);}cur = cur.children[index]; // go down }//mark end cur.setEnd();}// Returns if the word is in the trie.public boolean search(String word) {if(word == null || word.length() == 0) return false;TrieNode cur = root;for(int i = 0; i < word.length(); i++){char c = word.charAt(i);int index = c - 'a';if(cur.children[index] == null){//no such charreturn false;}cur = cur.children[index];}return cur.isEnd();}// Returns if there is any word in the trie// that starts with the given prefix.public boolean startsWith(String prefix) {if(prefix == null || prefix.length() == 0) return false;TrieNode cur = root;for(int i = 0; i < prefix.length(); i++){char c = prefix.charAt(i);int index = c - 'a';if(cur.children[index] == null){//no such charreturn false;}cur = cur.children[index];}return true;}} View Code
转载于:https://www.cnblogs.com/xiaomaoliu/p/4548195.html
总结
