Minimum Unique Word Abbreviation - Leetcode Solution

The Minimum Unique Word Abbreviation problem on LeetCode asks you to find the shortest abbreviation of a given word that is unique among a list of words.

The problem can be solved using a recursive approach where we take a letter from the word and either abbreviate it or leave it as it is. We then recursively apply this process to the remaining letters until we have exhausted all possible abbreviations.

We then check each abbreviation to see if it is unique among the list of words. If it is, we return it as the shortest unique abbreviation. If not, we continue looking for a shorter unique abbreviation.

Here is a detailed solution to the Minimum Unique Word Abbreviation problem:

First, we need a function to check if an abbreviation is unique among a list of words. We can use a set to store all the unique abbreviations of the words in the list.

def is_unique(abbr, words):
    unique_abbrs = set()
    for word in words:
        if len(word) != len(abbr):
            unique_abbrs.add(get_abbr(word, abbr))
    return abbr not in unique_abbrs

This function takes an abbreviation and a list of words as input. It creates a set to store all the unique abbreviations of the words in the list that have the same length as the abbreviation. It then calculates the abbreviation of each word using the get_abbr function (which we'll define shortly) and adds it to the set. Finally, it checks if the abbreviation we're testing is in the set of unique abbreviations. If it is not, then the abbreviation is unique and the function returns True. Otherwise, it returns False.

Now, we need a function to generate all possible abbreviations of a word.

def all_abbrs(word):
    if not word:
        return [""]
    abbrs = []
    for i in range(len(word)):
        for j in range(1, len(word)-i+1):
            abbr = word[:i] + str(j) + all_abbrs(word[i+j:])[0]
            abbrs.append(abbr)
    return abbrs

This function takes a word as input and generates all possible abbreviations of the word using a recursive approach. If the word is empty, it returns a list with a single empty string (which will be useful later). Otherwise, it loops over all possible starting positions for the abbreviated section of the word (i) and all possible lengths for the abbreviated section (j). It then generates the abbreviation by concatenating the prefix up to i, the length of the abbreviated section (j), and the abbreviations of the suffix after the abbreviated section (which are generated recursively using the same function). Finally, it appends the abbreviation to a list of all possible abbreviations and returns the list.

Now, we can define the main function that will solve the problem.

def min_abbr(word, dict):
    if word in dict:
        return word
    abbrs = all_abbrs(word)
    for i in range(1, len(word)+1):
        for abbr in abbrs:
            if len(abbr) == i and is_unique(abbr, dict):
                return abbr

This function takes a word and a list of words as input. If the word is already in the list, then it is its own unique abbreviation, and we can return it. Otherwise, we generate all possible abbreviations of the word using the all_abbrs function and loop over all possible lengths i of the unique abbreviation. For each length, we loop over all abbreviations of that length and check if they are unique using the is_unique function. If we find a unique abbreviation of the desired length, we return it as the shortest unique abbreviation.

This function has a time complexity of O(n * 2^n), where n is the length of the word, since we generate all possible abbreviations and check if they are unique. However, we can optimize this by using memoization to store the set of unique abbreviations for each length, so we only compute it once for each length. This reduces the time complexity to O(n * 2^n/2), which is much faster in practice.

1