288. Unique Word Abbreviation

Problem¶

Implement ValidWordAbbr(dictionary) and isUnique(word).

Abbreviate words longer than two characters as first letter + number of middle characters + last letter; shorter words remain unchanged. A query is unique if no different dictionary word has its abbreviation. Duplicate dictionary entries do not matter.

dictionary = ["deer", "door", "cake", "cake"]
abbreviations = {"d2r": {"deer", "door"}, "c2e": {"cake"}}

isUnique("deer") -> False  # Collides with "door".
isUnique("cake") -> True   # Repeated identical words are allowed.
isUnique("cart") -> True   # "c2t" is absent.

class ValidWordAbbr:
    def __init__(self, dictionary: list[str]):
        pass

    def isUnique(self, word: str) -> bool:
        pass

Key trick¶

Map each abbreviation to its sole distinct word, or None if multiple distinct words share it.

Trap¶

Dictionary membership alone does not imply uniqueness, duplicates are not collisions, and words of length one or two stay unchanged.

Why is it interesting?¶

It turns a repeated dictionary search into a constant-time lookup by storing exactly the information each query needs.

Python solution¶

class ValidWordAbbr:
    def __init__(self, dictionary: list[str]):
        # Each abbreviation maps to one word, or None for a collision.
        self.abbrevs = {}

        for word in dictionary:
            abbr = self._abbrev(word)
            if abbr not in self.abbrevs:
                self.abbrevs[abbr] = word
            elif self.abbrevs[abbr] != word:
                self.abbrevs[abbr] = None

    def _abbrev(self, word: str) -> str:
        if len(word) <= 2:
            return word
        return f"{word[0]}{len(word) - 2}{word[-1]}"

    def isUnique(self, word: str) -> bool:
        # An absent abbreviation or an identical sole owner is valid.
        return self.abbrevs.get(self._abbrev(word), word) == word

With word lengths bounded by 20 and \(n\) dictionary entries:

• Initialization: expected \(O(n)\) time.
• Query: expected \(O(1)\) time.
• Auxiliary space: \(O(n)\).

Comment on my solution¶

• isUnique is missing self; calling it as an instance method raises TypeError.
• Storing lists incorrectly rejects duplicates: with two copies of "cake", your method returns False for "cake".
• Your abbreviation logic correctly handles one-character words, but checking len(word) <= 2 is clearer.
• len(word[1:-1]) creates an unnecessary slice; use len(word) - 2 for longer words.

# WRONG
class ValidWordAbbr:
    def __init__(self, dictionary: list[str]):
        self.abbrevs = {}
        for s in dictionary:
            abbrev = self._abbrev(s)
            self.abbrevs.setdefault(abbrev, []).append(s)

    def _abbrev(self, word: str):
        cnt_midle = len(word[1:-1])
        midle = str(cnt_midle) if cnt_midle else ""
        end = "" if len(word) == 1 else word[len(word) - 1]
        return word[0] + midle + end

    def isUnique(word: str):
        abbrev = self._abbrev(word)
        if abbrev not in self.abbrevs:
            return True
        if len(self.abbrevs[abbrev]) == 1 and self.abbrevs[abbrev][0] == word:
            return True
        return False

Extra¶

Problem description¶

The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.

For example:

• dog --> d1g because there is one letter between the first letter 'd' and the last letter 'g'.
• internationalization --> i18n because there are 18 letters between the first letter 'i' and the last letter 'n'.
• it --> it because any word with only two characters is an abbreviation of itself.

Implement the ValidWordAbbr class:

• ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.
• boolean isUnique(string word) Returns true if either of the following conditions are met (otherwise returns false):
  • There is no word in dictionary whose abbreviation is equal to word's abbreviation.
  • For any word in dictionary whose abbreviation is equal to word's abbreviation, that word and word are the same.

Example 1:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

Constraints:

• 1 <= dictionary.length <= 3 * 10^4
• 1 <= dictionary[i].length <= 20
• dictionary[i] consists of lowercase English letters.
• 1 <= word.length <= 20
• word consists of lowercase English letters.
• At most 5000 calls will be made to isUnique.