Skip to main content

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