Skip to main content

Count the number of words with given prefix using Trie

Here given code implementation process.

/*
  Java program for
  Count the number of words with given prefix using Trie
*/
class TreeNode
{
    // Indicates end of string
    public boolean last;
    public TreeNode[] children;
    public TreeNode()
    {
        this.last = false;
        this.children = new TreeNode[26];
    }
}
public class Trie
{
    public TreeNode root;
    public Trie()
    {
        this.root = new TreeNode();
    }
    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
        TreeNode head = this.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 TreeNode();
            }
            // Visit to child node
            head = head.children[index];
        }
        if (head != null)
        {
            // Indicates end of string
            head.last = true;
        }
    }
    public int words(TreeNode head)
    {
        int counter = 0;
        if (head != null)
        {
            if (head.last == true)
            {
                counter++;
            }
            for (int i = 0; i < 26; i++)
            {
                if (head.children[i] != null)
                {
                    counter += words(head.children[i]);
                }
            }
        }
        return counter;
    }
    public void wordsByPrefix(String prefix)
    {
        TreeNode head = this.root;


        if (head != null)
        {
            // Display given prefix
            System.out.println(" Prefix : "+prefix);
            // Get the length of prefix
            int n = prefix.length();
            int level = 0;
            int index = 0;
            System.out.print(" Result : ");
            // Check that prefix exists in a trie tree
            while (level < n)
            {
                index = prefix.charAt(level) - 'a';
                if (head.children[index] != null)
                {
                  	// Visit to child node
                    head = head.children[index];
                }
                else
                {
                    // When prefix not exist
                    System.out.println(0);
                    return;
                }
                level++;
            }
            if (level == n)
            {
                if (head == null)
                {
                    System.out.println(1);
                }
                else
                {
                    System.out.println(words(head));
                }
            }
        }
    }
    public static void main(String[] args)
    {
        // Make tree
        Trie task = new Trie();
        // Tree Words
        task.insert("pincode");
        task.insert("ipcode");
        task.insert("pineapple");
        task.insert("pink");
        task.insert("pinch");
        task.insert("pinball");
        // Test A
        // Prefix : "pin"
        // pin -> ["pincode","pineapple","pink","pinch","pinball"]
        // Result : 5
        task.wordsByPrefix("pin");
        // Test B
        // Prefix : "pinc"
        // pin -> ["pincode","pinch"]
        // Result : 2
        task.wordsByPrefix("pinc");
    }
}

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
  C++ program for
  Count the number of words with given prefix using Trie
*/
class TreeNode
{
    public:
    // Indicates end of string
    bool last;
    TreeNode *children[26];
    TreeNode()
    {
        this->last = false;
        for (int i = 0; i < 26; ++i)
        {
            this->children[i] = NULL;
        }
    }
};
class Trie
{
    public: TreeNode *root;
    Trie()
    {
        this->root = new TreeNode();
    }
    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
        TreeNode *head = this->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 TreeNode();
            }
            // Visit to child node
            head = head->children[index];
        }
        if (head != NULL)
        {
            // Indicates end of string
            head->last = true;
        }
    }
    int words(TreeNode *head)
    {
        int counter = 0;
        if (head != NULL)
        {
            if (head->last == true)
            {
                counter++;
            }
            for (int i = 0; i < 26; i++)
            {
                if (head->children[i] != NULL)
                {
                    // Count prefix
                    counter += this->words(head->children[i]);
                }
            }
        }
        return counter;
    }
    void wordsByPrefix(string prefix)
    {
        TreeNode *head = this->root;
        if (head != NULL)
        {
            // Display given prefix
            cout << " Prefix : " << prefix << endl;
            // Get the length of prefix
            int n = prefix.length();
            int level = 0;
            int index = 0;
            cout << " Result : ";
            // Check that prefix exists in a trie tree
            while (level < n)
            {
                index = prefix[level] - 'a';
                if (head->children[index] != NULL)
                {
                    // Visit to child node
                    head = head->children[index];
                }
                else
                {
                    // When prefix not exist
                    cout << 0 << endl;
                    return;
                }
                level++;
            }
            if (level == n)
            {
                if (head == NULL)
                {
                    cout << 1 << endl;
                }
                else
                {
                    cout << this->words(head) << endl;
                }
            }
        }
    }
};
int main()
{
    // Make tree
    Trie *task = new Trie();
    // Tree Words
    task->insert("pincode");
    task->insert("ipcode");
    task->insert("pineapple");
    task->insert("pink");
    task->insert("pinch");
    task->insert("pinball");
    // Test A
    // Prefix : "pin"
    // pin->["pincode","pineapple","pink","pinch","pinball"]
    // Result : 5
    task->wordsByPrefix("pin");
    // Test B
    // Prefix : "pinc"
    // pin->["pincode","pinch"]
    // Result : 2
    task->wordsByPrefix("pinc");
    return 0;
}

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
package main
import "fmt"
/*
  Go program for
  Count the number of words with given prefix using Trie
*/
type TreeNode struct {
	// Indicates end of string
	last bool
	children [] *TreeNode 
}
func getTreeNode() * TreeNode {
	var me *TreeNode = &TreeNode {}
	me.last = false
	me.children = make([] *TreeNode, 26)
	return me
}
type Trie struct {
	root * TreeNode
}
func getTrie() * Trie {
	var me *Trie = &Trie {}
	me.root = getTreeNode()
	return me
}
func(this *Trie) insert(text string) {
	// First get the length of text
	var length int = len(text)
	// This variable are used to task find the index location of character
	var index int = 0
	// Get the root node
	var head * TreeNode = this.root
	for level := 0 ; level < length ; level++ {
		// Get the index
		index = int(text[level]) - int('a')
		if head.children[index] == nil {
			// When need to add new Node
			head.children[index] = getTreeNode()
		}
		// Visit to child node
		head = head.children[index]
	}
	if head != nil {
		// Indicates end of string
		head.last = true
	}
}
func(this Trie) words(head * TreeNode) int {
	var counter int = 0
	if head != nil {
		if head.last == true {
			counter++
		}
		for i := 0 ; i < 26 ; i++ {
			if head.children[i] != nil {
				// Count word
				counter += this.words(head.children[i])
			}
		}
	}
	return counter
}
func(this Trie) wordsByPrefix(prefix string) {
	var head * TreeNode = this.root
	if head != nil {
		// Display given prefix
		fmt.Println("Prefix : ", prefix)
		// Get the length of prefix
		var n int = len(prefix)
		var level int = 0
		var index int = 0
		fmt.Print("Result :  ")
		// Check that prefix exists in a trie tree
		for (level < n) {
			index = int(prefix[level]) - int('a')
			if head.children[index] != nil {
				// Visit to child node
				head = head.children[index]
			} else {
				// When prefix not exist
				fmt.Println(0)
				return
			}
			level++
		}
		if level == n {
			if head == nil {
				fmt.Println(1)
			} else {
				fmt.Println(this.words(head))
			}
		}
	}
}
func main() {
	// Make tree
	var task * Trie = getTrie()
	// Tree Words
	task.insert("pincode")
	task.insert("ipcode")
	task.insert("pineapple")
	task.insert("pink")
	task.insert("pinch")
	task.insert("pinball")
	// Test A
	// Prefix : "pin"
	// pin->["pincode","pineapple","pink","pinch","pinball"]
	// Result : 5
	task.wordsByPrefix("pin")
	// Test B
	// Prefix : "pinc"
	// pin->["pincode","pinch"]
	// Result : 2
	task.wordsByPrefix("pinc")
}

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
// Include namespace system
using System;
/*
  Csharp program for
  Count the number of words with given prefix using Trie
*/
public class TreeNode
{
	// Indicates end of string
	public Boolean last;
	public TreeNode[] children;
	public TreeNode()
	{
		this.last = false;
		this.children = new TreeNode[26];
	}
}
public class Trie
{
	public TreeNode root;
	public Trie()
	{
		this.root = new TreeNode();
	}
	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
		TreeNode head = this.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 TreeNode();
			}
			// Visit to child node
			head = head.children[index];
		}
		if (head != null)
		{
			// Indicates end of string
			head.last = true;
		}
	}
	public int words(TreeNode head)
	{
		int counter = 0;
		if (head != null)
		{
			if (head.last == true)
			{
				counter++;
			}
			for (int i = 0; i < 26; i++)
			{
				if (head.children[i] != null)
				{
					// Count word
					counter += this.words(head.children[i]);
				}
			}
		}
		return counter;
	}
	public void wordsByPrefix(String prefix)
	{
		TreeNode head = this.root;
		if (head != null)
		{
			// Display given prefix
			Console.WriteLine(" Prefix : " + prefix);
			// Get the length of prefix
			int n = prefix.Length;
			int level = 0;
			int index = 0;
			Console.Write(" Result : ");
			// Check that prefix exists in a trie tree
			while (level < n)
			{
				index = prefix[level] - 'a';
				if (head.children[index] != null)
				{
					// Visit to child node
					head = head.children[index];
				}
				else
				{
					// When prefix not exist
					Console.WriteLine(0);
					return;
				}
				level++;
			}
			if (level == n)
			{
				if (head == null)
				{
					Console.WriteLine(1);
				}
				else
				{
					Console.WriteLine(this.words(head));
				}
			}
		}
	}
	public static void Main(String[] args)
	{
		// Make tree
		Trie task = new Trie();
		// Tree Words
		task.insert("pincode");
		task.insert("ipcode");
		task.insert("pineapple");
		task.insert("pink");
		task.insert("pinch");
		task.insert("pinball");
		// Test A
		// Prefix : "pin"
		// pin->["pincode","pineapple","pink","pinch","pinball"]
		// Result : 5
		task.wordsByPrefix("pin");
		// Test B
		// Prefix : "pinc"
		// pin->["pincode","pinch"]
		// Result : 2
		task.wordsByPrefix("pinc");
	}
}

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
<?php
/*
  Php program for
  Count the number of words with given prefix using Trie
*/
class TreeNode
{
	// Indicates end of string
	public $last;
	public $children;
	public	function __construct()
	{
		$this->last = false;
		$this->children = array_fill(0, 26, NULL);
	}
}
class Trie
{
	public $root;
	public	function __construct()
	{
		$this->root = new TreeNode();
	}
	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 TreeNode();
			}
			// Visit to child node
			$head = $head->children[$index];
		}
		if ($head != NULL)
		{
			// Indicates end of string
			$head->last = true;
		}
	}
	public	function words($head)
	{
		$counter = 0;
		if ($head != NULL)
		{
			if ($head->last == true)
			{
				$counter++;
			}
			for ($i = 0; $i < 26; $i++)
			{
				if ($head->children[$i] != NULL)
				{
					// Count word
					$counter += $this->words($head->children[$i]);
				}
			}
		}
		return $counter;
	}
	public	function wordsByPrefix($prefix)
	{
		$head = $this->root;
		if ($head != NULL)
		{
			// Display given prefix
			echo(" Prefix : ".$prefix.
				"\n");
			// Get the length of prefix
			$n = strlen($prefix);
			$level = 0;
			$index = 0;
			echo(" Result : ");
			// Check that prefix exists in a trie tree
			while ($level < $n)
			{
				$index = ord($prefix[$level]) - ord('a');
				if ($head->children[$index] != NULL)
				{
					// Visit to child node
					$head = $head->children[$index];
				}
				else
				{
					// When prefix not exist
					echo("0 \n");
					return;
				}
				$level++;
			}
			if ($level == $n)
			{
				if ($head == NULL)
				{
					echo("1 \n");
				}
				else
				{
					echo($this->words($head)."\n");
				}
			}
		}
	}
}

function main()
{
	// Make tree
	$task = new Trie();
	// Tree Words
	$task->insert("pincode");
	$task->insert("ipcode");
	$task->insert("pineapple");
	$task->insert("pink");
	$task->insert("pinch");
	$task->insert("pinball");
	// Test A
	// Prefix : "pin"
	// pin->["pincode","pineapple","pink","pinch","pinball"]
	// Result : 5
	$task->wordsByPrefix("pin");
	// Test B
	// Prefix : "pinc"
	// pin->["pincode","pinch"]
	// Result : 2
	$task->wordsByPrefix("pinc");
}
main();

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
/*
  Node JS program for
  Count the number of words with given prefix using Trie
*/
class TreeNode
{
	constructor()
	{
		this.last = false;
		this.children = Array(26).fill(null);
	}
}
class Trie
{
	constructor()
	{
		this.root = new TreeNode();
	}
	insert(text)
	{
		// First get the length of text
		var length = text.length;
		// This variable are used to task find the index location of character
		var index = 0;
		// Get the root node
		var head = this.root;
		for (var level = 0; level < length; ++level)
		{
			// Get the index
			index = text.charAt(level).charCodeAt(0) - 
              		'a'.charCodeAt(0);
			if (head.children[index] == null)
			{
				// When need to add new Node
				head.children[index] = new TreeNode();
			}
			// Visit to child node
			head = head.children[index];
		}
		if (head != null)
		{
			// Indicates end of string
			head.last = true;
		}
	}
	words(head)
	{
		var counter = 0;
		if (head != null)
		{
			if (head.last == true)
			{
				counter++;
			}
			for (var i = 0; i < 26; i++)
			{
				if (head.children[i] != null)
				{
					// Count word
					counter += this.words(head.children[i]);
				}
			}
		}
		return counter;
	}
	wordsByPrefix(prefix)
	{
		var head = this.root;
		if (head != null)
		{
			// Display given prefix
			console.log(" Prefix : " + prefix);
			// Get the length of prefix
			var n = prefix.length;
			var level = 0;
			var index = 0;
			process.stdout.write(" Result : ");
			// Check that prefix exists in a trie tree
			while (level < n)
			{
				index = prefix.charAt(level).charCodeAt(0) - 
                  'a'.charCodeAt(0);
				if (head.children[index] != null)
				{
					// Visit to child node
					head = head.children[index];
				}
				else
				{
					// When prefix not exist
					console.log(0);
					return;
				}
				level++;
			}
			if (level == n)
			{
				if (head == null)
				{
					console.log(1);
				}
				else
				{
					console.log(this.words(head));
				}
			}
		}
	}
}

function main()
{
	// Make tree
	var task = new Trie();
	// Tree Words
	task.insert("pincode");
	task.insert("ipcode");
	task.insert("pineapple");
	task.insert("pink");
	task.insert("pinch");
	task.insert("pinball");
	// Test A
	// Prefix : "pin"
	// pin->["pincode","pineapple","pink","pinch","pinball"]
	// Result : 5
	task.wordsByPrefix("pin");
	// Test B
	// Prefix : "pinc"
	// pin->["pincode","pinch"]
	// Result : 2
	task.wordsByPrefix("pinc");
}
main();

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
#  Python 3 program for
#  Count the number of words with given prefix using Trie
class TreeNode :
	def __init__(self) :
    	#  Indicates end of string
		self.last = False
		self.children = [None] * (26)
	

class Trie :
	def __init__(self) :
		self.root = TreeNode()
	
	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] = TreeNode()
			
			#  Visit to child node
			head = head.children[index]
			level += 1
		
		if (head != None) :
			#  Indicates end of string
			head.last = True
		
	
	def words(self, head) :
		counter = 0
		if (head != None) :
			if (head.last == True) :
				counter += 1
			
			i = 0
			while (i < 26) :
				if (head.children[i] != None) :
					#  Count word
					counter += self.words(head.children[i])
				
				i += 1
			
		
		return counter
	
	def wordsByPrefix(self, prefix) :
		head = self.root
		if (head != None) :
			#  Display given prefix
			print(" Prefix : ", prefix)
			#  Get the length of prefix
			n = len(prefix)
			level = 0
			index = 0
			print(" Result :  ", end = "")
			#  Check that prefix exists in a trie tree
			while (level < n) :
				index = ord(prefix[level]) - ord('a')
				if (head.children[index] != None) :
					#  Visit to child node
					head = head.children[index]
				else :
					#  When prefix not exist
					print(0)
					return
				
				level += 1
			
			if (level == n) :
				if (head == None) :
					print(1)
				else :
					print(self.words(head))
				
			
		
	

def main() :
	#  Make tree
	task = Trie()
	#  Tree Words
	task.insert("pincode")
	task.insert("ipcode")
	task.insert("pineapple")
	task.insert("pink")
	task.insert("pinch")
	task.insert("pinball")
	#  Test A
	#  Prefix : "pin"
	#  pin->["pincode","pineapple","pink","pinch","pinball"]
	#  Result : 5
	task.wordsByPrefix("pin")
	#  Test B
	#  Prefix : "pinc"
	#  pin->["pincode","pinch"]
	#  Result : 2
	task.wordsByPrefix("pinc")

if __name__ == "__main__": main()

Output

 Prefix :  pin
 Result :  5
 Prefix :  pinc
 Result :  2
#  Ruby program for
#  Count the number of words with given prefix using Trie
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :last, :children
	attr_accessor :last, :children
	#  Indicates end of string
	Array.new() {nil}
	def initialize() 
		self.last = false
		self.children = Array.new(26) {nil}
	end

end

class Trie 
	# Define the accessor and reader of class Trie
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = TreeNode.new()
	end

	def insert(text) 
		#  First get the length of text
		length = text.length
		#  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 = text[level].ord - 'a'.ord
			if (head.children[index] == nil) 
				#  When need to add new Node
				head.children[index] = TreeNode.new()
			end

			#  Visit to child node
			head = head.children[index]
			level += 1
		end

		if (head != nil) 
			#  Indicates end of string
			head.last = true
		end

	end

	def words(head) 
		counter = 0
		if (head != nil) 
			if (head.last == true) 
				counter += 1
			end

			i = 0
			while (i < 26) 
				if (head.children[i] != nil) 
					#  Count word
					counter += self.words(head.children[i])
				end

				i += 1
			end

		end

		return counter
	end

	def wordsByPrefix(prefix) 
		head = self.root
		if (head != nil) 
			#  Display given prefix
			print(" Prefix : ", prefix, "\n")
			#  Get the length of prefix
			n = prefix.length
			level = 0
			index = 0
			print(" Result : ")
			#  Check that prefix exists in a trie tree
			while (level < n) 
				index = prefix[level].ord - 'a'.ord
				if (head.children[index] != nil) 
					#  Visit to child node
					head = head.children[index]
				else
 
					#  When prefix not exist
					print(0, "\n")
					return
				end

				level += 1
			end

			if (level == n) 
				if (head == nil) 
					print(1, "\n")
				else
 
					print(self.words(head), "\n")
				end

			end

		end

	end

end

def main() 
	#  Make tree
	task = Trie.new()
	#  Tree Words
	task.insert("pincode")
	task.insert("ipcode")
	task.insert("pineapple")
	task.insert("pink")
	task.insert("pinch")
	task.insert("pinball")
	#  Test A
	#  Prefix : "pin"
	#  pin->["pincode","pineapple","pink","pinch","pinball"]
	#  Result : 5
	task.wordsByPrefix("pin")
	#  Test B
	#  Prefix : "pinc"
	#  pin->["pincode","pinch"]
	#  Result : 2
	task.wordsByPrefix("pinc")
end

main()

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2

import scala.collection.mutable._;
/*
  Scala program for
  Count the number of words with given prefix using Trie
*/
class TreeNode(
	// Indicates end of string
	var last: Boolean,
		var children: Array[TreeNode])
{
	def this()
	{
		this(false, Array.fill[TreeNode](26)(null));
	}
}
class Trie(var root: TreeNode)
{
	def this()
	{
		this(new TreeNode());
	}
	def insert(text: String): Unit = {
		// First get the length of text
		var length: Int = text.length();
		// This variable are used to task find the index location of character
		var index: Int = 0;
		// Get the root node
		var head: TreeNode = this.root;
		var level: Int = 0;
		while (level < length)
		{
			// Get the index
			index = text.charAt(level).toInt - 'a'.toInt;
			if (head.children(index) == null)
			{
				// When need to add new Node
				head.children(index) = new TreeNode();
			}
			// Visit to child node
			head = head.children(index);
			level += 1;
		}
		if (head != null)
		{
			// Indicates end of string
			head.last = true;
		}
	}
	def words(head: TreeNode): Int = {
		var counter: Int = 0;
		if (head != null)
		{
			if (head.last == true)
			{
				counter += 1;
			}
			var i: Int = 0;
			while (i < 26)
			{
				if (head.children(i) != null)
				{
					// Count word
					counter += words(head.children(i));
				}
				i += 1;
			}
		}
		return counter;
	}
	def wordsByPrefix(prefix: String): Unit = {
		var head: TreeNode = this.root;
		if (head != null)
		{
			// Display given prefix
			println(" Prefix : " + prefix);
			// Get the length of prefix
			var n: Int = prefix.length();
			var level: Int = 0;
			var index: Int = 0;
			print(" Result : ");
			// Check that prefix exists in a trie tree
			while (level < n)
			{
				index = prefix.charAt(level).toInt - 'a'.toInt;
				if (head.children(index) != null)
				{
					// Visit to child node
					head = head.children(index);
				}
				else
				{
					// When prefix not exist
					println(0);
					return;
				}
				level += 1;
			}
			if (level == n)
			{
				if (head == null)
				{
					println(1);
				}
				else
				{
					println(words(head));
				}
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Make tree
		var task: Trie = new Trie();
		// Tree Words
		task.insert("pincode");
		task.insert("ipcode");
		task.insert("pineapple");
		task.insert("pink");
		task.insert("pinch");
		task.insert("pinball");
		// Test A
		// Prefix : "pin"
		// pin->["pincode","pineapple","pink","pinch","pinball"]
		// Result : 5
		task.wordsByPrefix("pin");
		// Test B
		// Prefix : "pinc"
		// pin->["pincode","pinch"]
		// Result : 2
		task.wordsByPrefix("pinc");
	}
}

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
import Foundation;
/*
  Swift 4 program for
  Count the number of words with given prefix using Trie
*/
class TreeNode
{
	// Indicates end of string
	var last: Bool;
	var children: [TreeNode?];
	init()
	{
		self.last = false;
		self.children = Array(repeating: nil, count: 26);
	}
}
class Trie
{
	var root: TreeNode? ;
	init()
	{
		self.root = TreeNode();
	}
	func insert(_ data: String)
	{
      	let text = Array(data);
		// First get the length of text
		let length: Int = text.count;
		// This variable are used to task find the index location of character
		var index: Int = 0;
		// Get the root node
		var head: TreeNode? = self.root;
		var level: Int = 0;
		while (level < length)
		{
			// Get the index
			index = Int(UnicodeScalar(String(text[level]))!.value) - 
              Int(UnicodeScalar(String("a"))!.value);
			if (head!.children[index] == nil)
			{
				// When need to add new Node
				head!.children[index] = TreeNode();
			}
			// Visit to child node
			head = head!.children[index];
			level += 1;
		}
		if (head  != nil)
		{
			// Indicates end of string
			head!.last = true;
		}
	}
	func words(_ head: TreeNode? ) -> Int
	{
		var counter: Int = 0;
		if (head  != nil)
		{
			if (head!.last == true)
			{
				counter += 1;
			}
			var i: Int = 0;
			while (i < 26)
			{
				if (head!.children[i]  != nil)
				{
					// Count word
					counter += self.words(head!.children[i]);
				}
				i += 1;
			}
		}
		return counter;
	}
	func wordsByPrefix(_ data: String)
	{
      	let prefix = Array(data);
		var head: TreeNode? = self.root;
		if (head  != nil)
		{
			// Display given prefix
			print(" Prefix : ", data);
			// Get the length of prefix
			let n: Int = prefix.count;
			var level: Int = 0;
			var index: Int = 0;
			print(" Result :  ", terminator: "");
			// Check that prefix exists in a trie tree
			while (level < n)
			{
				index = Int(UnicodeScalar(
                  String(prefix[level]))!.value) - 
                  Int(UnicodeScalar(String("a"))!.value);
				if (head!.children[index]  != nil)
				{
					// Visit to child node
					head = head!.children[index];
				}
				else
				{
					// When prefix not exist
					print(0);
					return;
				}
				level += 1;
			}
			if (level == n)
			{
				if (head == nil)
				{
					print(1);
				}
				else
				{
					print(self.words(head));
				}
			}
		}
	}
}
func main()
{
	// Make tree
	let task: Trie = Trie();
	// Tree Words
	task.insert("pincode");
	task.insert("ipcode");
	task.insert("pineapple");
	task.insert("pink");
	task.insert("pinch");
	task.insert("pinball");
	// Test A
	// Prefix : "pin"
	// pin->["pincode","pineapple","pink","pinch","pinball"]
	// Result : 5
	task.wordsByPrefix("pin");
	// Test B
	// Prefix : "pinc"
	// pin->["pincode","pinch"]
	// Result : 2
	task.wordsByPrefix("pinc");
}
main();

Output

 Prefix :  pin
 Result :  5
 Prefix :  pinc
 Result :  2
/*
  Kotlin program for
  Count the number of words with given prefix using Trie
*/
class TreeNode
{
	// Indicates end of string
	var last: Boolean;
	var children: Array < TreeNode ? > ;
	constructor()
	{
		this.last = false;
		this.children = Array(26)
		{
			null
		};
	}
}
class Trie
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = TreeNode();
	}
	fun insert(text: String): Unit
	{
		// First get the length of text
		val length: Int = text.length;
		// This variable are used to task find the index location of character
		var index: Int;
		// Get the root node
		var head: TreeNode ? = this.root;
		var level: Int = 0;
		while (level < length)
		{
			// Get the index
			index = text.get(level).toInt() - 'a'.toInt();
			if (head!!.children[index] == null)
			{
				// When need to add new Node
				head.children[index] = TreeNode();
			}
			// Visit to child node
			head = head.children[index];
			level += 1;
		}
		if (head != null)
		{
			// Indicates end of string
			head.last = true;
		}
	}
	fun words(head: TreeNode ? ): Int
	{
		var counter: Int = 0;
		if (head != null)
		{
			if (head.last == true)
			{
				counter += 1;
			}
			var i: Int = 0;
			while (i < 26)
			{
				if (head.children[i] != null)
				{
					// Count word
					counter += this.words(head.children[i]);
				}
				i += 1;
			}
		}
		return counter;
	}
	fun wordsByPrefix(prefix: String): Unit
	{
		var head: TreeNode ? = this.root;
		if (head != null)
		{
			// Display given prefix
			println(" Prefix : " + prefix);
			// Get the length of prefix
			val n: Int = prefix.length;
			var level: Int = 0;
			var index: Int ;
			print(" Result : ");
			// Check that prefix exists in a trie tree
			while (level < n)
			{
				index = prefix.get(level).toInt() - 'a'.toInt();
				if (head!!.children[index] != null)
				{
					// Visit to child node
					head = head.children[index];
				}
				else
				{
					// When prefix not exist
					println(0);
					return;
				}
				level += 1;
			}
			if (level == n)
			{
				if (head == null)
				{
					println(1);
				}
				else
				{
					println(this.words(head));
				}
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Make tree
	val task: Trie = Trie();
	// Tree Words
	task.insert("pincode");
	task.insert("ipcode");
	task.insert("pineapple");
	task.insert("pink");
	task.insert("pinch");
	task.insert("pinball");
	// Test A
	// Prefix : "pin"
	// pin->["pincode","pineapple","pink","pinch","pinball"]
	// Result : 5
	task.wordsByPrefix("pin");
	// Test B
	// Prefix : "pinc"
	// pin->["pincode","pinch"]
	// Result : 2
	task.wordsByPrefix("pinc");
}

Output

 Prefix : pin
 Result : 5
 Prefix : pinc
 Result : 2
Last updated on by Kalkicode




Comment

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