Posted on by Kalkicode
Code Tree

# Find shortest unique prefix for every word in a given list

The journey to find the shortest unique prefix for words in a given list leads us to the realm of Trie data structures. This article delves into the intriguing problem of crafting minimal yet distinguishing prefixes for a list of words. From problem definition to code implementation, this article takes you step by step through the process of solving this challenge.

## Problem Statement

Given a list of words, the goal is to determine the shortest prefixes that uniquely identify each word. If a prefix is shared among multiple words, it should be extended until a unique prefix is reached.

## Example

Consider the list of words: "bring", "workout", "break", "word", "works", and "wordlike". The resulting shortest unique prefixes are: "brea", "bres", "bri", "wordl", "worko", and "works".

## Idea to Solve

The problem is elegantly solved using a Trie data structure. A Trie allows us to efficiently store and search for strings. By navigating through the Trie, we can determine the shortest unique prefixes for each word.

## Pseudocode

1. Initialize an empty Trie.
2. For each word in the list:
• Insert the word into the Trie.
3. Traverse the Trie to find the shortest unique prefixes:
• For each node with only one child, append the corresponding character to the output.
• For nodes with multiple children, recursively explore further.

## Algorithm Explanation

1. Create a Trie data structure with a special flag 'last' indicating the end of a string.
2. For each word, insert its characters into the Trie while maintaining a count of characters traversing through that node.
3. Traverse the Trie recursively and:
• If a node has a count of 1, it indicates a unique prefix, so append the character to the output.
• If a node has multiple children, recursively explore each child node.

## Code Solution

``````/*
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
for (int level = 0; level < length; level++)
{
// Get the index
index = text.charAt(level) - 'a';
{
// When need to add new Node
}
else
{
}
}
{
// indicates end of string
}
}
public void shortestPrefix(TreeNode head, String output)
{
{
for (int i = 0; i < 26; ++i)
{
{
{
// 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

// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}
}``````

#### 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
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
{
// When need to add new Node
}
else
{
}
}
{
// indicates end of string
}
}
{
{
for (int i = 0; i < 26; ++i)
{
{
{
// Display Result
cout << output + ((char)(i + 97)) << endl;
}
else
{
// Find short prefix
this->shortestPrefix(
(((char)(i + 97))));
}
}
}
}
}
};
int main()
{
// Make Tree
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
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')
// When need to add new Node
} else {
}
}
// indicates end of string
}
}
func(this Trie) shortestPrefix(head * TreeNode, output string) {
for i := 0 ; i < 26 ; i++ {
// Display Result
fmt.Println(output+string(byte((i + 97))))
} else {
// Find short prefix
output + string((byte((i + 97)))))
}
}
}
}
}
func main() {
// Make Tree
var task * Trie = getTrie()
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}``````

#### 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
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
{
// When need to add new Node
}
else
{
}
}
{
// indicates end of string
}
}
public void shortestPrefix(TreeNode head, String output)
{
{
for (int i = 0; i < 26; ++i)
{
{
{
// Display Result
Console.WriteLine(output + ((char)(i + 97)));
}
else
{
// Find short prefix
output + ((char)(i + 97)));
}
}
}
}
}
public static void Main(String[] args)
{
// Make Tree
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}
}``````

#### 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
for (\$level = 0; \$level < \$length; \$level++)
{
// Get the index
\$index = ord(\$text[\$level]) - ord('a');
{
// When need to add new Node
}
else
{
}
}
{
// indicates end of string
}
}
{
{
for (\$i = 0; \$i < 26; ++\$i)
{
{
{
// Display Result
echo(\$output.(chr((\$i + 97))).
"\n");
}
else
{
// Find short prefix
\$output.strval((chr((\$i + 97)))));
}
}
}
}
}
}

function main()
{
// Make Tree
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}
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
for (var level = 0; level < length; level++)
{
// Get the index
index = text.charAt(level).charCodeAt(0) - 'a'.charCodeAt(0);
{
// When need to add new Node
}
else
{
}
}
{
// indicates end of string
}
}
{
{
for (var i = 0; i < 26; ++i)
{
{
{
// Display Result
console.log(output + (String.fromCharCode((i + 97))));
}
else
{
// Find short prefix
output + (String.fromCharCode((i + 97))));
}
}
}
}
}
}

function main()
{
// Make Tree
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}
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
level = 0
while (level < length) :
#  Get the index
index = ord(text[level]) - ord('a')
#  When need to add new Node
else :

level += 1

#  indicates end of string

i = 0
while (i < 26) :
#  Display Result
print(output + (chr((i + 97))))
else :
#  Find short prefix
output + str((chr((i + 97)))))

i += 1

def main() :
#  Make Tree
#  Test
#  ----
#    Scan "br"
#   "bring"
#    --
#   "break"
#    --│
#      ↓
#   "bress"   unique["bri", "brea","bres"]
#    --       Note "bre" common in ["break","bress"]
#  ------------------------------------------------------
#                     -      -      -
#   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"]

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_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_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
level = 0
while (level < length)
#  Get the index
index = text[level].ord - 'a'.ord
#  When need to add new Node
else
end

level += 1
end

#  indicates end of string
end

end

i = 0
while (i < 26)
#  Display Result
print(output + (((i + 97)).chr), "\n")
else

#  Find short prefix
output +(((i + 97)).chr).to_s)
end

end

i += 1
end

end

end

end

def main()
#  Make Tree
#  Test
#  ----
#    Scan "br"
#   "bring"
#    --
#   "break"
#    --│
#      ↓
#   "bress"   unique["bri", "brea","bres"]
#    --       Note "bre" common in ["break","bress"]
#  ------------------------------------------------------
#                     -      -      -
#   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"]
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 level: Int = 0;
while (level < length)
{
// Get the index
index = text.charAt(level).toInt - 'a'.toInt;
{
// When need to add new Node
}
else
{
}
level += 1;
}
{
// indicates end of string
}
}
def shortestPrefix(head: TreeNode, output: String): Unit = {
{
var i: Int = 0;
while (i < 26)
{
{
{
// Display Result
println(output + ((i + 97).toChar));
}
else
{
// Find short prefix
output + ((i + 97).toChar).toString());
}
}
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Make Tree
var task: Trie = new Trie();
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}
}``````

#### 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 level: Int = 0;
while (level < length)
{
// Get the index
index = Int(
UnicodeScalar(String(text[level]))!.value) -
Int(UnicodeScalar(String("a"))!.value
);
{
// When need to add new Node
}
else
{
}
level += 1;
}
{
// indicates end of string
}
}
func shortestPrefix(_ head: TreeNode? , _ output : String)
{
{
let startingValue = Int(("a" as UnicodeScalar).value); //97
var i: Int = 0;
while (i < 26)
{
{
{
// Display Result
print(output + String(Character(
UnicodeScalar(i + startingValue)!)));
}
else
{
// Find short prefix
output + String(Character(
UnicodeScalar(i + startingValue)!)));
}
}
i += 1;
}
}
}
}
func main()
{
// Make Tree
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}
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();
{
// When need to add new Node
}
else
{
}
level += 1;
}
{
// indicates end of string
}
}
fun shortestPrefix(head: TreeNode ? , output : String): Unit
{
{
var i: Int = 0;
while (i < 26)
{
{
{
// Display Result
println(output + ((i + 97).toChar()));
}
else
{
// Find short prefix
output + ((i + 97).toChar()).toString());
}
}
i += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
// Make Tree
// Test
// ----
//   Scan "br"
//  "bring"
//   --
//
//  "break"
//   --│
//     ↓
//  "bress"   unique["bri", "brea","bres"]
//   --       Note "bre" common in ["break","bress"]
// ------------------------------------------------------
//                    -      -      -
//  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"]
}``````

#### Output

``````brea
bres
bri
wordl
worko
works``````

## Time Complexity Analysis

The insertion of words into the Trie takes O(n * m) time, where n is the number of words and m is the average length of a word. The traversal to find the shortest unique prefixes also takes O(n * m) time in the worst case. Thus, the overall time complexity is O(n * m).

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

Categories
Relative Post