实现 trie 数据结构
trie数据结构的strider讲解
class node{ node [] node = new node[26]; boolean flag; public node(){ } public boolean containskey(char c){ return node[c-'a']!=null; } public void put(char c, node n){ node[c-'a'] = n; } public node get(char c){ return node[c-'a']; } public void setflag() { this.flag = true; } public boolean getflag(){ return this.flag; }}class trie { node root; public trie() { root = new node(); } //will take tc : o(len) of the word public void insert(string word) { node node = root; for(int i =0;i<word.length();i++){ if(!node.containskey(word.charat(i))){ node.put(word.charat(i),new node()); } node = node.get(word.charat(i)); } node.setflag(); } //will take tc : o(len) of the word public boolean search(string word) { node node = root; for(int i =0;i<word.length();i++){ if(!node.containskey(word.charat(i))){ return false; } node = node.get(word.charat(i)); } return node.getflag(); } //will take tc : o(len) of the prefix public boolean startswith(string prefix) { node node = root; for(int i =0;i<prefix.length();i++){ if(!node.containskey(prefix.charat(i))){ return false; } node = node.get(prefix.charat(i)); } return true; }}/** * 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); */
trie数据结构二
奋斗者的解释，以便更好理解
阿里云AI平台
阿里云AI平台
26 查看详情
import java.util.* ;import java.io.*; class node { node node[] = new node[26]; int endwith = 0;// will keep track of no. of words ending with this word int countprefix=0;// will keep track of no. of words starting with this word public node(){ } public boolean containskey(char c){ return node[c-'a']!=null; } public void put(char c, node n){ node[c-'a'] = n; } public node get(char c){ return node[c-'a']; } public void incrementcountprefix() { ++this.countprefix; } public void decrementcountprefix(){ --this.countprefix; } public void incrementendwith(){ ++this.endwith; } public void deleteendwith(){ --this.endwith; } public int getcountprefix(){ return this.countprefix; } public int getendwith(){ return this.endwith; }}public class trie { node root; public trie() { // write your code here. root = new node(); } public void insert(string word) { node node = root; for(int i =0;i<word.length();i++){ if(!node.containskey(word.charat(i))){ node.put(word.charat(i),new node()); } node = node.get(word.charat(i)); node.incrementcountprefix(); } node.incrementendwith(); } public int countwordsequalto(string word) { // write your code here. node node = root; for(int i=0;i<word.length();i++){ if(node.containskey(word.charat(i))){ node = node.get(word.charat(i)); } else return 0; } return node.getendwith();//this will tell how many strings are //ending with given word } public int countwordsstartingwith(string word) { node node = root; for(int i=0;i<word.length();i++){ if(node.containskey(word.charat(i))){ node = node.get(word.charat(i)); } else return 0; } return node.getcountprefix(); // it will tell how many strings are starting //with given word; } public void erase(string word) { node node = root; for(int i =0;i<word.length();i++){ if(node.containskey(word.charat(i))){ node = node.get(word.charat(i)); node.decrementcountprefix(); } else return; } node.deleteendwith(); }}
完整字符串
// tc : o(n*l)import java.util.* ;import java.io.*; class node{ node[] node = new node[26]; boolean flag; public node(){} public void put(char c , node n){ node[c-'a'] = n; } public boolean containskey(char c){ return node[c-'a']!=null; } public node get(char c){ return node[c-'a']; } public void setend(){ this.flag = true; } public boolean isend(){ return this.flag; }}class trie{ node root; public trie(){ root = new node(); } public boolean checkifprefixpresent(string s){ node node = root; boolean flag= true; for(int i = 0;i<s.length();i++){ char c = s.charat(i); if(!node.containskey(c)){ return false; } node = node.get(c); flag = flag && node.isend(); // this will check if the substring is also a string from the list of strings //if(flag == false) return false; // this line will also work here because if any substring is not present as a string in the trie , then // this string s won't be a complete string, and we can return false here only } return flag; } public void insert(string s){ node node = root; for(int i =0;i<s.length();i++){ char c = s.charat(i); if(!node.containskey(c)){ node.put(c, new node()); } node = node.get(c); } node.setend(); // setting end of the string as this is the //end of the current string s }}class solution { static node root; public static string completestring(int n, string[] a) { trie trie = new trie(); //storing all the string in the trie data structure for(string s : a) trie.insert(s); //finding out the comeplete string among all the list of strings string completestring = ""; for(string s : a){ if(trie.checkifprefixpresent(s)){ if(completestring.length() < s.length()){ completestring = s; } //lexographical selection : a.compareto(b) =-1 if a < b lexographically else if(completestring.length() == s.length() && s.compareto(completestring) < 0){ completestring = s; } } } return completestring.equals("") ? "none":completestring; }}
计算不同子串的个数
tc：在
中插入不同的唯一子字符串的 o(n^2)trie数据结构
import java.util.ArrayList;public class Solution { Node root; static int count; public Solution(){ root = new Node(); } public static int countDistinctSubstrings(String s) { count = 0; // Write your code here. Solution sol = new Solution(); for(int i =0;i< s.length();i++){ String str = ""; for (int j =i;j< s.length();j++){ str = str+s.charAt(j); sol.insert(str); } } return count+1; } public void insert(String s){ Node node = root; for(int i =0;i< s.length();i++){ if(!node.containsKey(s.charAt(i))){ node.put(s.charAt(i),new Node()); count++; } node = node.get(s.charAt(i)); } node.setFlag(); }}class Node { Node node[] = new Node[26]; boolean flag; public Node(){ } public boolean containsKey(char c){ return node[c-'a']!=null; } public Node get(char c){ return node[c-'a']; } public void put(char c, Node n){ node[c-'a'] = n; } public void setFlag(){ this.flag = true; } public boolean getFlag(){ return this.flag; }}
以上就是特里树的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/509021.html
微信扫一扫 
支付宝扫一扫 
