Count Total words in Trie

Count Total words in Trie

Here given code implementation process.

//C++ program
//Count Total words in Trie
#include <iostream>
#include <string.h>
using namespace std;
#define ALPHABETS 26
struct Node
{
  //Indicates end of string
  int end;
  struct Node *children[ALPHABETS];
};

class Trie
{

public:
  Node *root;
  Trie()
  {
    root = new Node;

    for (int i = 0; i < ALPHABETS; ++i)
    {
      root->children[i]=NULL;
    }
    root->end=0;
  }
  void insert(string);
  int  words(Node *root);
  
};

void Trie:: insert(string text)
{
  //First get the length of text
  int length = text.size();

  //This variable are used to task find the index location of character
  int index = 0;

  //Get the root node
  Node *head = root;

  for (int level = 0; level < length ; level++ )
  {

    //Get the index
    index = text[level]-'a';

    if(head->children[index] == NULL)
    {
      //When need to add new Node
      head->children[index]= new Node;


      for (int i = 0; i < ALPHABETS; ++i)
      {
        head->children[index]->children[i]=NULL;
      }
      head->children[index]->end=0;
    }

    head =head->children[index];
  }
  if(head != NULL)
  {  
    //Indicates end of string
    head->end = 1;
  }

}

int Trie:: words(Node *root)
  {
    int counter = 0;
    if(root!=NULL)
    {

      if(root->end==1)
      {
        counter++;
      }
      for (int i = 0; i < ALPHABETS ; i++ ) 
      {
        if(root->children[i] != NULL)
        {
          counter += words(root->children[i]);
        }    
      }

    }
    return counter;
  }
int main()
{
  //Make object
  Trie obj ;
  obj.insert("how");
  obj.insert("many");
  obj.insert("code");
  obj.insert("co");
  obj.insert("club");
  obj.insert("run");
  obj.insert("rule");
  obj.insert("set");
 
  

  /*
         root  

     /  / |  \    \
    /  /  |   \    \ 
   /  /   |    \    \
  h   m   c     r    s
  |   |   | \   |    |
  o   a   o  l  u    e
  |   |  /|  |  | \  |
  w   n # d  u  n  l t
      |   |  |     |
      y   e  b     e
  */
  cout<<" Total Words : "<<obj.words(obj.root);


  return 0;
}

Output

Total Words : 8
/*
Java program
Count Total words in Trie
*/
class Node
{
  //Indicates end of string
  public boolean end;

  public Node []children;

  public Node(int size)
  {
    children = new Node[size];
    end = false;
  }
}
public class Trie 
{ 
  static final int ALPHABETS = 26;

  public Node root; 

  public Trie()
  {
    root = new Node(ALPHABETS);
  }

  public void insert(String text)
  {
    //First get the length of text
    int length = text.length();

    //This variable are used to task find the index location of character
    int index = 0;

    //Get the root node
    Node head = root;

    for (int level = 0; level < length ; level++ )
    {
      //Get the index
      index = text.charAt(level)-'a';

      if(head.children[index] == null)
      {
        //When need to add new Node
        head.children[index] = new Node(ALPHABETS);
      }

      head = head.children[index];
    }
    if(head != null)
    {  
      //indicates end of string
      head.end = true;
    }
  }
  public int words(Node root)
  {
    int counter = 0;
    if(root!=null)
    {

      if(root.end==true)
      {
        counter++;
      }
      for (int i = 0; i < ALPHABETS ; i++ ) 
      {
        if(root.children[i] != null)
        {
          counter += words(root.children[i]);
        }    
      }

    }
    return counter;
  }

  public static void main(String[] args) 
  {
    //Make object
    Trie obj = new Trie();
     
    obj.insert("how");
    obj.insert("many");
    obj.insert("code");
    obj.insert("co");
    obj.insert("club");
    obj.insert("run");
    obj.insert("rule");
    obj.insert("set");
   
    

/*
           root  

       /  / |  \    \
      /  /  |   \    \ 
     /  /   |    \    \
    h   m   c     r    s
    |   |   | \   |    |
    o   a   o  l  u    e
    |   |  /|  |  | \  |
    w   n # d  u  n  l t
        |   |  |     |
        y   e  b     e
    */

    System.out.println(" Total Words : "+obj.words(obj.root));


  }
}

Output

 Total Words : 8
#Python program
#Count Total words in Trie
class Node:
  def __init__(self,size):
    self.children=[None]*size
    self.end=False

    
class Trie:

  def __init__(self):
    self.ALPHABET = 26
    self.root=Node(self.ALPHABET)

  
  def insert(self,text) :

    #First get the length of text
    length=len(text)
    #This variable are used to task find the index location of character
    index=0
    #Get the root node
    head= self.root
    level=0
    while ( level< length  ) :

      #Get the index
      index=ord(text[level])-ord('a')

      if (head.children[index]== None) :

        #When need to add new Node
        head.children[index]= Node(self.ALPHABET)
      head= head.children[index]

      level+=1
    if(head != None) :

      #Indicates end of string
      head.end= True

  def words(self,root) :

    counter = 0
    if(root!=None) :

      if(root.end==True) :

        counter += 1
      i = 0
      while (i < self.ALPHABET )  :

        if(root.children[i] != None) :

          counter += self.words(root.children[i])
        i += 1
    return counter

def main():
  obj = Trie()

  obj.insert("how")
  obj.insert("many")
  obj.insert("code")
  obj.insert("co")
  obj.insert("club")
  obj.insert("run")
  obj.insert("rule")
  obj.insert("set")
  #
  #         root
  #     /  / |  \    \
  #    /  /  |   \    \
  #   /  /   |    \    \
  #  h   m   c     r    s
  #  |   |   | \   |    |
  #  o   a   o  l  u    e
  #  |   |  /|  |  | \  |
  #  w   n # d  u  n  l t
  #      |   |  |     |
  #      y   e  b     e
  #  
  print(" Total Words : ",obj.words(obj.root))


if __name__=="__main__":
  main()

Output

 Total Words :  8
/*
C# program
Count Total words in Trie
*/
using System;
public class Node
{
  //Indicates end of string
  public Boolean end;

  public Node []children;

  public Node(int size)
  {
    children = new Node[size];
    end = false;
  }
}
public class Trie 
{ 
  public const int ALPHABETS = 26;

  public Node root; 

  public Trie()
  {
    root = new Node(ALPHABETS);
  }

  public void insert(String text)
  {
    //First get the.Length of text
    int length = text.Length;

    //This variable are used to task find the index location of character
    int index = 0;

    //Get the root node
    Node head = root;

    for (int level = 0; level < length ; level++ )
    {
      //Get the index
      index = text[level]-'a';

      if(head.children[index] == null)
      {
        //When need to add new Node
        head.children[index] = new Node(ALPHABETS);
      }

      head = head.children[index];
    }
    if(head != null)
    {  
      //indicates end of string
      head.end = true;
    }
  }
  public int words(Node root)
  {
    int counter = 0;
    if(root!=null)
    {

      if(root.end==true)
      {
        counter++;
      }
      for (int i = 0; i < ALPHABETS ; i++ ) 
      {
        if(root.children[i] != null)
        {
          counter += words(root.children[i]);
        }    
      }

    }
    return counter;
  }

  public static void Main(String[] args) 
  {
    //Make object
    Trie obj = new Trie();

    obj.insert("how");
    obj.insert("many");
    obj.insert("code");
    obj.insert("co");
    obj.insert("club");
    obj.insert("run");
    obj.insert("rule");
    obj.insert("set");



    /*
           root  

       /  / |  \    \
      /  /  |   \    \ 
     /  /   |    \    \
    h   m   c     r    s
    |   |   | \   |    |
    o   a   o  l  u    e
    |   |  /|  |  | \  |
    w   n # d  u  n  l t
        |   |  |     |
        y   e  b     e
    */

    Console.WriteLine(" Total Words : "+obj.words(obj.root));


  }
}

Output

 Total Words : 8
<?php 
/*
* PHP Program 
* Count Total words in Trie
*/


class Node
{
  public $end;
  public $children;
  function __construct($size)
  {
    $this->children=array_fill(0, $size, NULL);
    $this->end=false;

  }
}
class Trie
{

  public $root;
  const ALPHABET = 26;

  function __construct()
  {
    $this->root=new Node(self:: ALPHABET);
  }


  public function  insert($text)
  {
    //First get the length of text
    $length=strlen($text);

    //This variable are used to task find the index location of character
    $index=0;

    //Get the root node
    $head= $this->root;

    for ($level=0; $level< $length; ++$level)
    {

      //Get the index
      $index=ord($text[$level])-ord('a');


      if ($head->children[$index]== NULL)
      {
        //When need to add new Node
        $head->children[$index]= new  Node(self::ALPHABET);
      }

      $head= $head->children[$index];
    }
    if($head != NULL)
    {  
      //Indicates end of string
      $head->end= true;
    }
  }
  public function words($root)
  {
    $counter = 0;
    if($root!=NULL)
    {

      if($root->end==true)
      {
        $counter++;
      }
      for ( $i = 0; $i < self::ALPHABET ; $i++ ) 
      {
        if($root->children[$i] != NULL)
        {
          $counter += $this->words($root->children[$i]);
        }    
      }

    }
    return $counter;
  }

}


function main()
{
  //Make object
  $obj = new Trie();


  $obj->insert("how");
  $obj->insert("many");
  $obj->insert("code");
  $obj->insert("co");
  $obj->insert("club");
  $obj->insert("run");
  $obj->insert("rule");
  $obj->insert("set");

  

  /*
         root  

     /  / |  \    \
    /  /  |   \    \ 
   /  /   |    \    \
  h   m   c     r    s
  |   |   | \   |    |
  o   a   o  l  u    e
  |   |  /|  |  | \  |
  w   n # d  u  n  l t
      |   |  |     |
      y   e  b     e
  */
  echo " Total Words : ".$obj->words($obj->root);
}
main();
?>

Output

 Total Words : 8

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved