Skip to main content

Find a longest length word in Trie

Here given code implementation process.

/*
  C++ program
  Find a longest length word in Trie
*/
//Include header file
#include <iostream>

using namespace std;
#define ALPHABETS 26
//This is tire tree node
class Node
{
	public:
		//Indicates stop of string
		bool stop;
	Node *children[ALPHABETS];
	Node()
	{
		this->stop = false;
		for (int i = 0; i < ALPHABETS; ++i)
		{
			this->children[i] = NULL;
		}
	}
};
class Trie
{
	public: Node *root;
	Trie()
	{
		this->root = new Node();
	}
	//This function are add new element 
	void 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 = 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 Node();
			}
			head = head->children[index];
		}
		if (head != NULL)
		{
			//indicates stop of string
			head->stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	string longest_word(Node *root, string about)
	{
		string text = about, temp = "";
		if (root != NULL)
		{
			for (int i = 0; i < ALPHABETS; i++)
			{
				temp = "";
				if (root->children[i] != NULL)
				{
					temp = longest_word(root->children[i], about + ((char)(i + 97)));
				}
				if (temp.size() > text.size())
				{
					text = temp;
				}
			}
		}
		if (text.size() > about.size())
		{
			return text;
		}
		else
		{
			return about;
		}
	}
};
int main()
{
	//Make object of Tree
	Trie obj = Trie();
	//Add following nodes in trie tree
	obj.insert("cool");
	obj.insert("coder");
	obj.insert("confirm");
	obj.insert("child");
	cout << "Longest word is : " << obj.longest_word(obj.root, "");
	return 0;
}

Output

Longest word is : confirm
/*
  Java program
  Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
	//Indicates stop of string
	public boolean stop;
	public Node[] children;
	public Node(int size)
	{
		this.stop = false;
		this.children = new Node[size];
	}
}
class Trie
{
	public int alphabets;
	public Node root;
	public Trie()
	{
		this.alphabets = 26;
		this.root = new Node(this.alphabets);
	}
	//This function are add new element 
	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(this.alphabets);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	public String longest_word(Node root, String about)
	{
		String text = about, temp = "";
		if (root != null)
		{
			for (int i = 0; i < this.alphabets; i++)
			{
				temp = "";
				if (root.children[i] != null)
				{
					temp = longest_word(root.children[i], about + ((char)(i + 97)));
				}
				if (temp.length() > text.length())
				{
					text = temp;
				}
			}
		}
		if (text.length() > about.length())
		{
			return text;
		}
		else
		{
			return about;
		}
	}
	public static void main(String[] args)
	{
		//Make object of Tree
		Trie obj = new Trie();
		//Add following nodes in trie tree
		obj.insert("cool");
		obj.insert("coder");
		obj.insert("confirm");
		obj.insert("child");
		System.out.println("Longest word is : " + obj.longest_word(obj.root, ""));
	}
}

Output

Longest word is : confirm
/*
  C# program
  Find a longest length word in Trie
*/
//Include namespace system
using System;
//This is tire tree node
public class Node
{
	//Indicates stop of string
	public Boolean stop;
	public Node[] children;
	public Node(int size)
	{
		this.stop = false;
		this.children = new Node[size];
	}
}
class Trie
{
	public int alphabets;
	public Node root;
	public Trie()
	{
		this.alphabets = 26;
		this.root = new Node(this.alphabets);
	}
	//This function are add new element 
	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(this.alphabets);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	public String longest_word(Node root, String about)
	{
		String text = about, temp = "";
		if (root != null)
		{
			for (int i = 0; i < this.alphabets; i++)
			{
				temp = "";
				if (root.children[i] != null)
				{
					temp = longest_word(root.children[i], about + ((char)(i + 97)));
				}
				if (temp.Length > text.Length)
				{
					text = temp;
				}
			}
		}
		if (text.Length > about.Length)
		{
			return text;
		}
		else
		{
			return about;
		}
	}
	public static void Main(String[] args)
	{
		//Make object of Tree
		Trie obj = new Trie();
		//Add following nodes in trie tree
		obj.insert("cool");
		obj.insert("coder");
		obj.insert("confirm");
		obj.insert("child");
		Console.WriteLine("Longest word is : " + obj.longest_word(obj.root, ""));
	}
}

Output

Longest word is : confirm
# 
#   Python 3 program
#   Find a longest length word in Trie

# This is tire tree node
class Node :
  # Indicates stop of string
  
  def __init__(self, size) :
    self.stop = False
    self.children = [None]*size
  

class Trie :
  
  def __init__(self) :
    self.alphabets = 26
    self.root = Node(self.alphabets)
  
  # This function are add new element 
  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.alphabets)
      
      head = head.children[index]
      level += 1
    
    if (head != None) :
      # indicates stop of string
      head.stop = True
    
  
  # This function are finding largest word length string in given tire tree
  def longest_word(self, root, about) :
    text = about
    temp = ""
    if (root != None) :
      i = 0
      while (i < self.alphabets) :
        temp = ""
        if (root.children[i] != None) :
          temp = self.longest_word(root.children[i], about + ((chr(i + 97))))
        
        if (len(temp) > len(text)) :
          text = temp
        
        i += 1
      
    
    if (len(text) > len(about)) :
      return text
    else :
      return about
    
  

def main() :
  # Make object of Tree
  obj = Trie()
  # Add following nodes in trie tree
  obj.insert("cool")
  obj.insert("coder")
  obj.insert("confirm")
  obj.insert("child")

  print("Longest word is : ", obj.longest_word(obj.root, ""), end = "")

if __name__ == "__main__": 
  main()

Output

Longest word is :  confirm
#   Ruby program
#   Find a longest length word in Trie

# This is tire tree node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :stop, :children
	attr_accessor :stop, :children

	# Indicates stop of string
	def initialize(size)
	
		self.stop = false
		self.children = Array.new(size){nil}
	end
end
class Trie 

	# Define the accessor and reader of class Trie  
	attr_reader :alphabets, :root
	attr_accessor :alphabets, :root
	
	def initialize()
	
		self.alphabets = 26
		self.root = Node.new(self.alphabets)
	end
	# This function are add new element 
	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 = @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] = Node.new(self.alphabets)
			end
			head = head.children[index]
			level += 1
		end
		if (head != nil)
		
			# indicates stop of string
			head.stop = true
		end
	end
	# This function are finding largest word length string in given tire tree
	def longest_word(root, about)
	
		text = about
		temp = ""
		if (root != nil)
		
			i = 0
			while (i < self.alphabets)
			
				temp = ""
				if (root.children[i] != nil)
				
					temp = self.longest_word(root.children[i], about + (((i + 97)).chr))
				end
				if (temp.length() > text.length())
				
					text = temp
				end
				i += 1
			end
		end
		if (text.length() > about.length())
		
			return text
		else
		
			return about
		end
	end
end
def main()

	# Make object of Tree
	obj = Trie.new()
	# Add following nodes in trie tree
	obj.insert("cool")
	obj.insert("coder")
	obj.insert("confirm")
	obj.insert("child")
	print("Longest word is : ", obj.longest_word(obj.root, ""))
end
main()

Output

Longest word is : confirm
/*
  Scala program
  Find a longest length word in Trie
*/
//This is tire tree node
class Node(var stop: Boolean,
	var children: Array[Node])
{
	def this(size: Int)
	{
		this(false, Array.fill[Node](size)(null));
	}
}
class Trie(var alphabets: Int,
	var root: Node)
{
	def this()
	{
		this(26, new Node(26));
	}
	//This function are add new element 
	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: Node = root;
		var level: Int = 0;
		while (level < length)
		{
			//Get the index
			index = text(level) - 'a';
			if (head.children(index) == null)
			{
				//When need to add new Node
				head.children(index) = new Node(this.alphabets);
			}
			head = head.children(index);
			level += 1;
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	def longest_word(root: Node, about: String): String = {
		var text: String = about;
		var temp: String = "";
		if (root != null)
		{
			var i: Int = 0;
			while (i < this.alphabets)
			{
				temp = "";
				if (root.children(i) != null)
				{
					temp = longest_word(root.children(i), about + ((i + 97).toChar));
				}
				if (temp.length() > text.length())
				{
					text = temp;
				}
				i += 1;
			}
		}
		if (text.length() > about.length())
		{
			return text;
		}
		else
		{
			return about;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object of Tree
		var obj: Trie = new Trie();
		//Add following nodes in trie tree
		obj.insert("cool");
		obj.insert("coder");
		obj.insert("confirm");
		obj.insert("child");
		print("Longest word is : " + obj.longest_word(obj.root, ""));
	}
}

Output

Longest word is : confirm
/*
  Swift program
  Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
	//Indicates stop of string
	var stop: Bool;
	var children: [Node? ] = [Node]();
	init(_ size: Int)
	{
		self.stop = false;
		var i = 0;
		while (i < size)
		{
			self.children.append(nil);
			i += 1;
		}
	}
}
class Trie
{
	var alphabets: Int;
	var root: Node? ;
	init()
	{
		self.alphabets = 26;
		self.root = Node(self.alphabets);
	}
	//This function are add new element 
	func insert(_ data: String)
	{
		//first get the length of text
		let length: Int = data.count;
		let text = Array(data);
		//This variable are used to task find the index location of character
		var index: Int = 0;
		//get the root node
		var head: Node? = self.root;
		var level: Int = 0;
		while (level < length)
		{
			//Get the index
			index = Int(UnicodeScalar(String(text[level]))!.value - 
                        UnicodeScalar("a")!.value);
			if (head!.children[index] == nil)
			{
				//When need to add new Node
				head!.children[index] = Node(self.alphabets);
			}
			head = head!.children[index];
			level += 1;
		}
		if (head != nil)
		{
			//indicates stop of string
			head!.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	func longest_word(_ root: Node? , _ about : String) -> String
	{
		var text: String = about;
		var temp: String = "";
		if (root != nil)
		{
			var i: Int = 0;
			while (i < self.alphabets)
			{
				temp = "";
				if (root!.children[i] != nil)
				{
					temp = self.longest_word(root!.children[i], about + (String(UnicodeScalar(UInt8((i + 97))))));
				}
				if (temp.count > text.count)
				{
					text = temp;
				}
				i += 1;
			}
		}
		if (text.count > about.count)
		{
			return text;
		}
		else
		{
			return about;
		}
	}
}
func main()
{
	//Make object of Tree
	let obj: Trie = Trie();
	//Add following nodes in trie tree
	obj.insert("cool");
	obj.insert("coder");
	obj.insert("confirm");
	obj.insert("child");
	print("Longest word is : ", obj.longest_word(obj.root, ""), terminator: "");
}
main();

Output

Longest word is :  confirm
<?php
/*
  Php program
  Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
  //Indicates stop of string
  public $stop;
  public $children;

  function __construct($size)
  {
    $this->stop = false;
    $this->children = array_fill(0, $size, null);
  }
}
class Trie
{
  public $alphabets;
  public $root;

  function __construct()
  {
    $this->alphabets = 26;
    $this->root = new Node($this->alphabets);
  }
  //This function are add new element 
  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($this->alphabets);
      }
      $head = $head->children[$index];
    }
    if ($head != null)
    {
      //indicates stop of string
      $head->stop = true;
    }
  }
  //This function are finding largest word length string in given tire tree
  public  function longest_word($root, $about)
  {
    $text = $about;
    $temp = "";
    if ($root != null)
    {
      for ($i = 0; $i < $this->alphabets; $i++)
      {
        $temp = "";
        if ($root->children[$i] != null)
        {
          $temp = $this->longest_word($root->children[$i], $about . chr((($i + 97))));
        }
        if (strlen($temp) > strlen($text))
        {
          $text = $temp;
        }
      }
    }
    if (strlen($text) > strlen($about))
    {
      return $text;
    }
    else
    {
      return $about;
    }
  }
}

function main()
{
  //Make object of Tree
  $obj = new Trie();
  //Add following nodes in trie tree
  $obj->insert("cool");
  $obj->insert("coder");
  $obj->insert("confirm");
  $obj->insert("child");
  echo "Longest word is : ". $obj->longest_word($obj->root, "");
}
main();

Output

Longest word is : confirm
/*
  Node Js program
  Find a longest length word in Trie
*/
//This is tire tree node
class Node
{
	constructor(size)
	{
		this.stop = false;
		this.children = Array(size).fill(null);
	}
}
class Trie
{
	constructor()
	{
		this.alphabets = 26;
		this.root = new Node(this.alphabets);
	}
	//This function are add new element 
	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.charCodeAt(level) - 'a'.charCodeAt(0);
			if (head.children[index] == null)
			{
				//When need to add new Node
				head.children[index] = new Node(this.alphabets);
			}
			head = head.children[index];
		}
		if (head != null)
		{
			//indicates stop of string
			head.stop = true;
		}
	}
	//This function are finding largest word length string in given tire tree
	longest_word(root, about)
	{
		var text = about;
		var temp = "";
		if (root != null)
		{
			for (var i = 0; i < this.alphabets; i++)
			{
				temp = "";
				if (root.children[i] != null)
				{
					temp = this.longest_word(root.children[i], about + String.fromCharCode(((i + 97))));
				}
				if (temp.length > text.length)
				{
					text = temp;
				}
			}
		}
		if (text.length > about.length)
		{
			return text;
		}
		else
		{
			return about;
		}
	}
}

function main()
{
	//Make object of Tree
	var obj = new Trie();
	//Add following nodes in trie tree
	obj.insert("cool");
	obj.insert("coder");
	obj.insert("confirm");
	obj.insert("child");
	process.stdout.write("Longest word is : " + obj.longest_word(obj.root, ""));
}
main();

Output

Longest word is : confirm
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