Trie データ構造の実装

トライデータ構造の説明

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

  
  
  データ構造を試す II


より理解を深めるためのストリバーの説明


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

  
  
  完全な文字列




// 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

  
  
  個別の部分文字列を数える


Tc: 
 に異なる一意の部分文字列を挿入する場合は O(n^2)
データ構造を試す


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