Shortest Unique Prefix Editorial

Practice Problem Link: Shortest Unique Prefix

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a list of words. You need to find the shortest prefix of each word so that it can identify the word uniquely.

Naive Approach

In the naive approach, we can try all the possible prefixes of all the words and check which prefix of the given word can act as its shortest unique prefix. In this way, we can generate the list of shortest unique prefixes of all the words.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(n)

Optimal Approach

In the optimal approach, we will use the "Trie" data structure. We will make a Trie of all the characters from the given list of strings, and also store the frequency of each character being inserted into the “Trie”. Now the prefix of each string will be the string, which is up to the character closest to the root and having a frequency of one. This way, using a DFS on the Trie, we can form our required shortest common prefixes.

Analysis

• Time Complexity:  O(n) 
• Space Complexity: O(n)

Implementation

C++

class TrieNode{
	public:
	vector<TrieNode*> characters;
	vector<int> count;
	bool isEndOfWord;
	TrieNode(){
	for(int i = 0; i < 26; i++){
		count.push_back(0);
		characters.push_back(NULL);
	}
		isEndOfWord = false;
	}
};
void insert(string word, TrieNode* root){
	TrieNode* node = root;
	for(int i = 0; i < word.size(); i++) {
		if(node->characters[word[i] - 'a'] != NULL) {
			node->count[word[i] - 'a'] += 1;
			node = node->characters[word[i] - 'a'];
		} else{
			TrieNode* newNode = new TrieNode();
			newNode->isEndOfWord = false;
			node->characters[word[i] - 'a'] = newNode;
			node->count[word[i] - 'a'] += 1;
			node = newNode;
		}
	}
}
string find(string word, TrieNode* root){
	TrieNode* node = root;
	string answer = "";
	for(int i = 0; i < word.size(); i++){
		if(node->count[word[i] - 'a'] == 1){
			answer += word[i];
			return answer;
		}
		else{
			answer += word[i];
			node = node->characters[word[i] - 'a'];
		}
	}
	return answer;
}
vector<string> getShortestUniquePrefixes(vector<string> &words) {
	TrieNode* root = new TrieNode();
	for(int i = 0; i < words.size(); i++) {
		insert(words[i], root);
	}
	vector<string> answer (words.size());
	for(int i = 0; i < words.size(); i++) {
		answer[i] = find(words[i], root);
	}
	return answer;
}

Java

class Solution {
	public static class TrieNode{
		TrieNode[] characters = new TrieNode[26];
		int[] count = new int[26];
		boolean isEndOfWord;
		TrieNode(){
			for(int i = 0; i < 26; i++){
				count[i] = 0;
				characters[i] = null;
			}
			isEndOfWord = false;
		}
	}
	void insert(String word, TrieNode root){
		TrieNode node = root;
		for(int i = 0; i < word.length(); i++) {
			if(node.characters[word.charAt(i) - 'a'] != null) {
				node.count[word.charAt(i) - 'a'] += 1;
				node = node.characters[word.charAt(i) - 'a'];
			}
			else{
				TrieNode newNode = new TrieNode();
				newNode.isEndOfWord = false;
				node.characters[word.charAt(i) - 'a'] = newNode;
				node.count[word.charAt(i) - 'a'] += 1;
				node = newNode;
			}
		}
	}
	String find(String word, TrieNode root){
		TrieNode node = root;
		String answer = "";
		for(int i = 0;i < word.length(); i++){
			if(node.count[word.charAt(i) - 'a'] == 1){
				answer += word.charAt(i);
				return answer;
			}
			else{
				answer += word.charAt(i);
				node = node.characters[word.charAt(i) - 'a'];
			}
		}
		return answer;
	}
	String[] getShortestUniquePrefixes(String[] words) {
		TrieNode root = new TrieNode();
		for(int i = 0; i < words.length; i++) {
			insert(words[i], root);
		}
		String[] answer = new String[words.length];
		for(int i = 0; i < words.length; i++) {
			answer[i] = find(words[i], root);
		}
		return answer;
	}
	
}