Frontend School

Find Shortest Unique Prefixes

DSA
medium

Find Shortest Unique Prefixes

Medium
Trie
String
Algorithms

Overview

In applications like contact managers, dictionary lookups, or command-line auto-completion, efficiently identifying the most concise and unambiguous way to refer to an item is crucial. This problem challenges you to process a list of words and determine the shortest possible prefix for each word such that this prefix is unique across the entire list. This ensures clarity and reduces user input while maintaining distinctness.

What you need to do / Task

You are given an array of strings, words. Your task is to return an array of strings, where each element is the shortest unique prefix for the corresponding word in the input words array.

A prefix P of a word W is considered "unique" if no other word W' (where W' is not W itself) in the input words array has P as its prefix.

Input & output

  • Input:
    • words: An array of strings (string[]). Each string consists of lowercase English letters.
  • Output:
    • An array of strings (string[]) of the same length as words. Each string at index i should be the shortest unique prefix for words[i].

Clarifications

  • All input words will consist of lowercase English letters.
  • The input words array will not be empty.
  • Words in the input array are guaranteed to be unique.
  • If a word itself is the shortest unique prefix (e.g., no other word starts with it, or it's a prefix of a longer word), then the entire word should be returned as its unique prefix.

Examples

1

Example 1

Input:

words = ["zebra", "dog", "duck", "dove"]

Output:

["z", "dog", "duc", "dov"]

Note:

  • For "zebra", 'z' is unique.
  • For "dog", "dog" itself is unique.
  • For "duck", 'd' is shared by "dog", "duck", "dove". 'du' is shared by "duck", "dove". 'duc' is unique.
  • For "dove", 'd' is shared. 'do' is shared by "dog", "dove". 'dov' is unique.
2

Example 2

Input:

words = ["apple", "apricot", "banana", "apply"]

Output:

["apple", "apr", "b", "apply"]

Note:

  • For "apple", "apple" itself is unique (no other word starts with "apple").
  • For "apricot", 'a', 'ap' are shared. 'apr' is unique.
  • For "banana", 'b' is unique.
  • For "apply", "apply" itself is unique (no other word starts with "apply").
3

Example 3

Input:

words = ["cat", "car", "cart"]

Output:

["cat", "car", "cart"]

Note:

  • For "cat", "cat" is unique (not a prefix of "car" or "cart").
  • For "car", "car" is unique (not a prefix of "cat"; while "car" is a prefix of "cart", the definition excludes the word itself from comparison, and "cart" is not "car").
  • For "cart", "cart" is unique (not a prefix of "cat" or "car").

Constraints

Constraints & assumptions

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 30
  • All characters in words[i] are lowercase English letters ('a'-'z').
  • All words in the input array words are unique.

What interviewers evaluate

  • Trie Construction: Ability to correctly build a Trie data structure, including relevant node properties (e.g., character mapping, frequency counts).
  • Algorithm Design: Correctly identify and implement the logic to find the shortest unique prefix using the Trie's properties.
  • Time & Space Complexity: Analyze and optimize the solution's performance, aiming for efficient handling of string operations and large inputs.
  • Code Quality: Write clean, readable, and well-structured code with appropriate variable names and comments where necessary.

Loading editor...