Find the shortest unique prefix for every word in a given list in Java
Finding the shortest unique prefix for each word in a given list is a common problem in computer science, particularly useful in applications like autocomplete systems, dictionaries, and search engines. The task involves identifying the minimal prefix of each word such that no two words in the list share the same prefix. The above problem not only helps in minimizing the amount of data stored but also optimizes the search and retrieval processes. By ensuring that each word can be uniquely identified by its shortest prefix, we can enhance both efficiency and user experience in various text-processing applications. The following discussion delves into the methods and algorithms used to solve the above problem, highlighting their practical implementations and computational efficiency.
Example:
Input: words = {program code process coding type print}
Output: {"prog", "code", "proc", "codi", "t", "pri"}
Explanation: The algorithm involves inserting words into a Trie, traversing each character, creating new Trie nodes if necessary, and updating the count of each node. It then finds unique prefixes by building the prefix string until reaching a node with a count of 1, indicating a unique prefix. The output is a list of unique prefixes, such as "prog code proc codi t pri".
Using Trie Approach
Algorithm
Step1: Create a root node with an array of children and a count initialized to 0.
Step2: Traverse each character, calculate the index, create a new node if the child node is null, move to the child node, and increase the count of the current node.
Step3: Initialize an empty prefix string, traverse each character of the word, append the character to the prefix, move to the corresponding child node, stop traversing if the count of the current node is 1, and store the prefix.
Step4: Print all unique prefixes as a space-separated string.
Here is an implementation of finding the shortest unique prefix for every word in a given list using the trie approach:
FileName:UniquePrefixFinder.java
import java.util.*; public class UniquePrefixFinder { static final int ALPHABET_SIZE = 26; // Alphabet size for lowercase 'a' to 'z' static class TrieNode { TrieNode[] children = new TrieNode[ALPHABET_SIZE]; // Array to store child nodes int count; TrieNode() { count = 0; // Initial count is 0 for (int i = 0; i < ALPHABET_SIZE; i++) { children[i] = null; // Initialize all child nodes to null } } } static TrieNode root; // Root of the Trie // Method to add a word to the Trie static void addWord(String word) { TrieNode currentNode = root; // Traverse each character in the word for (char c : word.toCharArray()) { int index = c - 'a'; // Calculate index for the character // If the child node does not exist, create a new node if (currentNode.children[index] == null) { currentNode.children[index] = new TrieNode(); } currentNode = currentNode.children[index]; currentNode.count++; // Increment the count for the current node } } // Method to get the unique prefix of a word static String getUniquePrefix(String word) { TrieNode currentNode = root; StringBuilder prefix = new StringBuilder(); // Traverse each character in the word for (char c : word.toCharArray()) { int index = c - 'a'; // Calculate index for the character prefix.append(c); // Append character to the prefix currentNode = currentNode.children[index]; // If the current node count is 1, it is a unique prefix if (currentNode.count == 1) { break; } } return prefix.toString(); // Return the unique prefix } public static void main(String[] args) { String input = "program code process coding type print"; String[] words = input.split(" "); root = new TrieNode(); // Add words to the Trie for (String word : words) { addWord(word); } // Find and print unique prefixes for each word Listresult = new ArrayList<>(); for (String word : words) { result.add(getUniquePrefix(word)); } System.out.println(String.join(" ", result)); } }
Output:
prog code proc codi t pri
Complexity analysis: The above approach has a time complexity of O(N x M) due to the time required to insert and process each word and a space complexity of O(N x M) due to the space required to store the Trie.