Find shortest unique prefix for every word in a given list
Here given code implementation process.
/*
Java program
Find shortest unique prefix for every word in a given list
*/
class TreeNode
{
// Indicates end of string
public boolean last;
public TreeNode[] children;
public int count;
public TreeNode()
{
this.last = false;
this.children = new TreeNode[26];
this.count = 1;
}
}
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();
}
else
{
head.children[index].count++;
}
head = head.children[index];
}
if (head != null)
{
// indicates end of string
head.last = true;
}
}
public void shortestPrefix(TreeNode head, String output)
{
if (head != null)
{
for (int i = 0; i < 26; ++i)
{
if (head.children[i] != null)
{
if (head.children[i].count == 1)
{
// Display Result
System.out.println(output + ((char)(i + 97)));
}
else
{
// Find short prefix
shortestPrefix(head.children[i], output + ((char)(i + 97)));
}
}
}
}
}
public static void main(String[] args)
{
// Make Tree
Trie task = new Trie();
// Add word
task.insert("bring");
task.insert("workout");
task.insert("break");
task.insert("word");
task.insert("works");
task.insert("wordlike");
task.insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "");
}
}
Output
brea
bres
bri
wordl
worko
works
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ program
Find shortest unique prefix for every word in a given list
*/
class TreeNode
{
public:
// Indicates end of string
bool last;
TreeNode *children[26];
int count;
TreeNode()
{
this->last = false;
for (int i = 0; i < 26; ++i)
{
this->children[i] = NULL;
}
this->count = 1;
}
};
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();
}
else
{
head->children[index]->count++;
}
head = head->children[index];
}
if (head != NULL)
{
// indicates end of string
head->last = true;
}
}
void shortestPrefix(TreeNode *head, string output)
{
if (head != NULL)
{
for (int i = 0; i < 26; ++i)
{
if (head->children[i] != NULL)
{
if (head->children[i]->count == 1)
{
// Display Result
cout << output + ((char)(i + 97)) << endl;
}
else
{
// Find short prefix
this->shortestPrefix(
head->children[i], output +
(((char)(i + 97))));
}
}
}
}
}
};
int main()
{
// Make Tree
Trie *task = new Trie();
// Add word
task->insert("bring");
task->insert("workout");
task->insert("break");
task->insert("word");
task->insert("works");
task->insert("wordlike");
task->insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task->shortestPrefix(task->root, "");
return 0;
}
Output
brea
bres
bri
wordl
worko
works
package main
import "fmt"
/*
Go program
Find shortest unique prefix for every word in a given list
*/
type TreeNode struct {
// Indicates end of string
last bool
children [] *TreeNode
count int
}
func getTreeNode() * TreeNode {
var me *TreeNode = &TreeNode {}
me.last = false
me.children = make([] *TreeNode, 26)
me.count = 1
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()
} else {
head.children[index].count++
}
head = head.children[index]
}
if head != nil {
// indicates end of string
head.last = true
}
}
func(this Trie) shortestPrefix(head * TreeNode, output string) {
if head != nil {
for i := 0 ; i < 26 ; i++ {
if head.children[i] != nil {
if head.children[i].count == 1 {
// Display Result
fmt.Println(output+string(byte((i + 97))))
} else {
// Find short prefix
this.shortestPrefix(head.children[i],
output + string((byte((i + 97)))))
}
}
}
}
}
func main() {
// Make Tree
var task * Trie = getTrie()
// Add word
task.insert("bring")
task.insert("workout")
task.insert("break")
task.insert("word")
task.insert("works")
task.insert("wordlike")
task.insert("bress")
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "")
}
Output
brea
bres
bri
wordl
worko
works
// Include namespace system
using System;
/*
Csharp program
Find shortest unique prefix for every word in a given list
*/
public class TreeNode
{
// Indicates end of string
public Boolean last;
public TreeNode[] children;
public int count;
public TreeNode()
{
this.last = false;
this.children = new TreeNode[26];
this.count = 1;
}
}
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();
}
else
{
head.children[index].count++;
}
head = head.children[index];
}
if (head != null)
{
// indicates end of string
head.last = true;
}
}
public void shortestPrefix(TreeNode head, String output)
{
if (head != null)
{
for (int i = 0; i < 26; ++i)
{
if (head.children[i] != null)
{
if (head.children[i].count == 1)
{
// Display Result
Console.WriteLine(output + ((char)(i + 97)));
}
else
{
// Find short prefix
this.shortestPrefix(head.children[i],
output + ((char)(i + 97)));
}
}
}
}
}
public static void Main(String[] args)
{
// Make Tree
Trie task = new Trie();
// Add word
task.insert("bring");
task.insert("workout");
task.insert("break");
task.insert("word");
task.insert("works");
task.insert("wordlike");
task.insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "");
}
}
Output
brea
bres
bri
wordl
worko
works
<?php
/*
Php program
Find shortest unique prefix for every word in a given list
*/
class TreeNode
{
// Indicates end of string
public $last;
public $children;
public $count;
public function __construct()
{
$this->last = false;
$this->children = array_fill(0, 26, NULL);
$this->count = 1;
}
}
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();
}
else
{
$head->children[$index]->count++;
}
$head = $head->children[$index];
}
if ($head != NULL)
{
// indicates end of string
$head->last = true;
}
}
public function shortestPrefix($head, $output)
{
if ($head != NULL)
{
for ($i = 0; $i < 26; ++$i)
{
if ($head->children[$i] != NULL)
{
if ($head->children[$i]->count == 1)
{
// Display Result
echo($output.(chr(($i + 97))).
"\n");
}
else
{
// Find short prefix
$this->shortestPrefix($head->children[$i],
$output.strval((chr(($i + 97)))));
}
}
}
}
}
}
function main()
{
// Make Tree
$task = new Trie();
// Add word
$task->insert("bring");
$task->insert("workout");
$task->insert("break");
$task->insert("word");
$task->insert("works");
$task->insert("wordlike");
$task->insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
$task->shortestPrefix($task->root, "");
}
main();
Output
brea
bres
bri
wordl
worko
works
/*
Node JS program
Find shortest unique prefix for every word in a given list
*/
class TreeNode
{
constructor()
{
this.last = false;
this.children = Array(26).fill(null);
this.count = 1;
}
}
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();
}
else
{
head.children[index].count++;
}
head = head.children[index];
}
if (head != null)
{
// indicates end of string
head.last = true;
}
}
shortestPrefix(head, output)
{
if (head != null)
{
for (var i = 0; i < 26; ++i)
{
if (head.children[i] != null)
{
if (head.children[i].count == 1)
{
// Display Result
console.log(output + (String.fromCharCode((i + 97))));
}
else
{
// Find short prefix
this.shortestPrefix(head.children[i],
output + (String.fromCharCode((i + 97))));
}
}
}
}
}
}
function main()
{
// Make Tree
var task = new Trie();
// Add word
task.insert("bring");
task.insert("workout");
task.insert("break");
task.insert("word");
task.insert("works");
task.insert("wordlike");
task.insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "");
}
main();
Output
brea
bres
bri
wordl
worko
works
# Python 3 program
# Find shortest unique prefix for every word in a given list
class TreeNode :
def __init__(self) :
# Indicates end of string
self.last = False
self.children = [None] * (26)
self.count = 1
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()
else :
head.children[index].count += 1
head = head.children[index]
level += 1
if (head != None) :
# indicates end of string
head.last = True
def shortestPrefix(self, head, output) :
if (head != None) :
i = 0
while (i < 26) :
if (head.children[i] != None) :
if (head.children[i].count == 1) :
# Display Result
print(output + (chr((i + 97))))
else :
# Find short prefix
self.shortestPrefix(head.children[i],
output + str((chr((i + 97)))))
i += 1
def main() :
# Make Tree
task = Trie()
# Add word
task.insert("bring")
task.insert("workout")
task.insert("break")
task.insert("word")
task.insert("works")
task.insert("wordlike")
task.insert("bress")
# Test
# ----
# ➀ ["bring","break","bress"] this start with "br"
# Scan "br"
# "bring"
# --
# "break"
# --│
# ↓
# "bress" unique["bri", "brea","bres"]
# -- Note "bre" common in ["break","bress"]
# ------------------------------------------------------
# - - -
# ➁ ["word","wordlike",workout","works"] this start with "wor"
# Scan "wor"
# "word"
# ---│
# ↓
# "wordlike"
# Common in both is "word" unique ["wordl"]
# Note not taken "word" because after d no character
# "workout"
# ---│
# ↓
# "works"
# Common in both is "work" unique ["worko","works"]
# ------------------------------------------------------
# Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "")
if __name__ == "__main__": main()
Output
brea
bres
bri
wordl
worko
works
# Ruby program
# Find shortest unique prefix for every word in a given list
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :last, :children, :count
attr_accessor :last, :children, :count
# Indicates end of string
Array.new() {nil}
def initialize()
self.last = false
self.children = Array.new(26) {nil}
self.count = 1
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()
else
head.children[index].count += 1
end
head = head.children[index]
level += 1
end
if (head != nil)
# indicates end of string
head.last = true
end
end
def shortestPrefix(head, output)
if (head != nil)
i = 0
while (i < 26)
if (head.children[i] != nil)
if (head.children[i].count == 1)
# Display Result
print(output + (((i + 97)).chr), "\n")
else
# Find short prefix
self.shortestPrefix(head.children[i],
output +(((i + 97)).chr).to_s)
end
end
i += 1
end
end
end
end
def main()
# Make Tree
task = Trie.new()
# Add word
task.insert("bring")
task.insert("workout")
task.insert("break")
task.insert("word")
task.insert("works")
task.insert("wordlike")
task.insert("bress")
# Test
# ----
# ➀ ["bring","break","bress"] this start with "br"
# Scan "br"
# "bring"
# --
# "break"
# --│
# ↓
# "bress" unique["bri", "brea","bres"]
# -- Note "bre" common in ["break","bress"]
# ------------------------------------------------------
# - - -
# ➁ ["word","wordlike",workout","works"] this start with "wor"
# Scan "wor"
# "word"
# ---│
# ↓
# "wordlike"
# Common in both is "word" unique ["wordl"]
# Note not taken "word" because after d no character
# "workout"
# ---│
# ↓
# "works"
# Common in both is "work" unique ["worko","works"]
# ------------------------------------------------------
# Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "")
end
main()
Output
brea
bres
bri
wordl
worko
works
import scala.collection.mutable._;
/*
Scala program
Find shortest unique prefix for every word in a given list
*/
class TreeNode(
// Indicates end of string
var last: Boolean,
var children: Array[TreeNode],
var count: Int)
{
def this()
{
this(false, Array.fill[TreeNode](26)(null), 1);
}
}
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();
}
else
{
head.children(index).count += 1;
}
head = head.children(index);
level += 1;
}
if (head != null)
{
// indicates end of string
head.last = true;
}
}
def shortestPrefix(head: TreeNode, output: String): Unit = {
if (head != null)
{
var i: Int = 0;
while (i < 26)
{
if (head.children(i) != null)
{
if (head.children(i).count == 1)
{
// Display Result
println(output + ((i + 97).toChar));
}
else
{
// Find short prefix
shortestPrefix(head.children(i),
output + ((i + 97).toChar).toString());
}
}
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Make Tree
var task: Trie = new Trie();
// Add word
task.insert("bring");
task.insert("workout");
task.insert("break");
task.insert("word");
task.insert("works");
task.insert("wordlike");
task.insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "");
}
}
Output
brea
bres
bri
wordl
worko
works
import Foundation;
/*
Swift 4 program
Find shortest unique prefix for every word in a given list
*/
class TreeNode
{
// Indicates end of string
var last: Bool;
var children: [TreeNode?];
var count: Int;
init()
{
self.last = false;
self.children = Array(repeating: nil, count: 26);
self.count = 1;
}
}
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();
}
else
{
head!.children[index]!.count += 1;
}
head = head!.children[index];
level += 1;
}
if (head != nil)
{
// indicates end of string
head!.last = true;
}
}
func shortestPrefix(_ head: TreeNode? , _ output : String)
{
if (head != nil)
{
let startingValue = Int(("a" as UnicodeScalar).value); //97
var i: Int = 0;
while (i < 26)
{
if (head!.children[i] != nil)
{
if (head!.children[i]!.count == 1)
{
// Display Result
print(output + String(Character(
UnicodeScalar(i + startingValue)!)));
}
else
{
// Find short prefix
self.shortestPrefix(head!.children[i],
output + String(Character(
UnicodeScalar(i + startingValue)!)));
}
}
i += 1;
}
}
}
}
func main()
{
// Make Tree
let task: Trie = Trie();
// Add word
task.insert("bring");
task.insert("workout");
task.insert("break");
task.insert("word");
task.insert("works");
task.insert("wordlike");
task.insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "");
}
main();
Output
brea
bres
bri
wordl
worko
works
/*
Kotlin program
Find shortest unique prefix for every word in a given list
*/
class TreeNode
{
// Indicates end of string
var last: Boolean;
var children: Array < TreeNode ? > ;
var count: Int;
constructor()
{
this.last = false;
this.children = Array(26)
{
null
};
this.count = 1;
}
}
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();
}
else
{
head.children[index]!!.count += 1;
}
head = head.children[index];
level += 1;
}
if (head != null)
{
// indicates end of string
head.last = true;
}
}
fun shortestPrefix(head: TreeNode ? , output : String): Unit
{
if (head != null)
{
var i: Int = 0;
while (i < 26)
{
if (head.children[i] != null)
{
if (head.children[i]!!.count == 1)
{
// Display Result
println(output + ((i + 97).toChar()));
}
else
{
// Find short prefix
this.shortestPrefix(head.children[i],
output + ((i + 97).toChar()).toString());
}
}
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
// Make Tree
val task: Trie = Trie();
// Add word
task.insert("bring");
task.insert("workout");
task.insert("break");
task.insert("word");
task.insert("works");
task.insert("wordlike");
task.insert("bress");
// Test
// ----
// ➀ ["bring","break","bress"] this start with "br"
// Scan "br"
// "bring"
// --
//
// "break"
// --│
// ↓
// "bress" unique["bri", "brea","bres"]
// -- Note "bre" common in ["break","bress"]
// ------------------------------------------------------
// - - -
// ➁ ["word","wordlike",workout","works"] this start with "wor"
// Scan "wor"
// "word"
// ---│
// ↓
// "wordlike"
// Common in both is "word" unique ["wordl"]
// Note not taken "word" because after d no character
// "workout"
// ---│
// ↓
// "works"
// Common in both is "work" unique ["worko","works"]
// ------------------------------------------------------
// Result : [ "brea", "bres", "bri", "wordl", "worko", "works"]
task.shortestPrefix(task.root, "");
}
Output
brea
bres
bri
wordl
worko
works
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