We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Abbreviation

Number: 527

Difficulty: Hard

Paid? Yes

Companies: Google, Snap

Problem Description

Given an array of distinct strings, the goal is to generate the minimal unique abbreviation for every word. An abbreviation follows these rules:

  1. The initial abbreviation for each word is the first character + the count of characters between the first and last letter + the last character.
  2. If two or more words share the same abbreviation, their prefixes are extended (by one additional character) until all abbreviations in that group become unique.
  3. If the abbreviation does not reduce the string’s length, the original word is kept.

Key Insights

  • Start with a one-character prefix and form the abbreviation as: first letter + (length - prefix - 1) + last letter.
  • Group words sharing the same abbreviation. For groups with collisions, increase the prefix length.
  • For each word in a collision group, compare with every other word in the same group to determine the minimum required prefix length (common prefix length + 1).
  • Once every abbreviation is unique and shorter than the original word, return the result.
  • If the abbreviation does not reduce the length, simply use the original word.

Space and Time Complexity

Time Complexity: O(n^2 * L) in the worst-case where n is the number of words and L is the maximum length (due to pairwise common prefix comparisons in groups). Space Complexity: O(n) for storing new abbreviations and prefix lengths.

Solution

We will use an iterative approach with the following strategy:

  1. Initialize an array to keep track of the current prefix length for each word, starting from 1.
  2. Generate an abbreviation for each word using its current prefix length.
  3. Use a hashmap (or dictionary) to group words by their abbreviation.
  4. For each group with more than one word, update the prefix length for every word by comparing it with every other word in the same group and calculating the length of the common prefix plus one.
  5. Repeat the above steps until all abbreviations are unique.
  6. Finally, if an abbreviation does not shorten the word (i.e., its length is not less than the original), use the original word.

This algorithm mainly leverages dictionary groupings and pairwise comparisons for resolving conflicts.

Code Solutions

# Python solution for Word Abbreviation

from typing import List

class Solution:
    def wordsAbbreviation(self, words: List[str]) -> List[str]:
        n = len(words)
        # Helper function to compute abbreviation given a word and prefix length.
        def abbreviate(word: str, prefix: int) -> str:
            # Check if abbreviation is shorter than the word.
            if prefix >= len(word) - 2:  # need at least 1 char in between
                return word
            abbr = word[:prefix] + str(len(word) - prefix - 1) + word[-1]
            return abbr if len(abbr) < len(word) else word

        # Helper function to compute common prefix length between two words.
        def commonPrefix(word1: str, word2: str) -> int:
            i = 0
            while i < len(word1) and i < len(word2) and word1[i] == word2[i]:
                i += 1
            return i

        # Each word starts with a prefix of length 1.
        prefix = [1] * n
        ans = [""] * n
        
        # While we still have collisions.
        while True:
            lookup = {}
            # Group words by their current abbreviation.
            for i in range(n):
                abbr = abbreviate(words[i], prefix[i])
                if abbr not in lookup:
                    lookup[abbr] = []
                lookup[abbr].append(i)
            
            unique = True
            # Process each group that has a collision.
            for abbr, indices in lookup.items():
                if len(indices) > 1:
                    unique = False
                    # For each pair in the group, update prefix length.
                    for i in indices:
                        for j in indices:
                            if i == j:
                                continue
                            common = commonPrefix(words[i], words[j])
                            # Increase prefix to common prefix length + 1 if needed.
                            prefix[i] = max(prefix[i], common + 1)
            if unique:
                break

        # Form final answers.
        for i in range(n):
            candidate = abbreviate(words[i], prefix[i])
            ans[i] = candidate
        return ans

# Example usage:
# sol = Solution()
# print(sol.wordsAbbreviation(["like","god","internal","me","internet","interval","intension","face","intrusion"]))
← Back to All Questions