Katkat
Back

Find Shortest Unique Prefixes

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently manage and query prefix-based string sets using a Trie (prefix tree) data structure.

Problem Statement

Given a list of words, find the shortest unique prefix for each word. A unique prefix of a word is the shortest substring starting from the beginning of the word that does not appear as a prefix of any other word in the input list. If a word is a prefix of another word, it will not have a unique prefix; in such cases, return the full word itself.

Function Signature

def find_shortest_unique_prefixes(words: List[str]) -> List[str]:

Constraints

  • 1 <= len(words) <= 10^4
  • 1 <= len(words[i]) <= 100
  • The input contains only lowercase English letters.

Examples

Example 1: Input: ["zebra", "dog", "duck", "dove"] Output: ["z", "dog", "du", "dov"] Explanation:

  • "z" is enough to identify "zebra".
  • "dog" is the full word because "d" and "do" are prefixes of "dove" and "duck".
  • "du" distinguishes "duck" from "dove".
  • "dov" distinguishes "dove" from "duck".

Example 2: Input: ["apple", "apply"] Output: ["apple", "apply"]

Edge Cases

  • Empty input list.
  • A word is a prefix of another word (as seen in Example 2).
  • Duplicate words in the input list.

Hints

Hint 1

Consider building a Trie where each node stores a count of how many times it has been visited during the insertion of all words.

Hint 2

During insertion, increment a counter at each node in the path representing the current word.

Hint 3

To find the shortest unique prefix, traverse the Trie for each word and stop at the first node that has a visit count of 1.

Follow-up questions

  • How would you modify your solution if the list of words was extremely large and couldn't fit in memory?
  • What is the time and space complexity of your Trie-based approach in terms of the total number of characters N across all words?
  • How would you handle a scenario where you need to update the list of words dynamically (adding or removing words)?