特里树

实现 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数据结构二

奋斗者的解释，以便更好理解

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;
    }
}