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