Unique Word Abbreviation
Problem
An abbreviation of a word follows the form <first><len(middle)><last>. Build a structure over a dictionary that returns whether a word's abbreviation is unique — i.e., no other dictionary word abbreviates to the same string.
dict=["deer","door","cake","card"]; isUnique("dear")falseclass ValidWordAbbr:
def __init__(self, dictionary):
self.m = {}
for w in set(dictionary):
key = self._abbr(w)
self.m.setdefault(key, set()).add(w)
def _abbr(self, w):
return w if len(w) <= 2 else f"{w[0]}{len(w)-2}{w[-1]}"
def isUnique(self, w):
key = self._abbr(w)
bucket = self.m.get(key, set())
return not bucket or (len(bucket) == 1 and w in bucket)class ValidWordAbbr {
constructor(dict) {
this.m = new Map();
for (const w of new Set(dict)) {
const key = this._abbr(w);
if (!this.m.has(key)) this.m.set(key, new Set());
this.m.get(key).add(w);
}
}
_abbr(w) {
return w.length <= 2 ? w : w[0] + (w.length - 2) + w[w.length - 1];
}
isUnique(w) {
const b = this.m.get(this._abbr(w)) || new Set();
return b.size === 0 || (b.size === 1 && b.has(w));
}
}class ValidWordAbbr {
Map> m = new HashMap<>();
public ValidWordAbbr(String[] dict) {
for (String w : new HashSet<>(Arrays.asList(dict))) {
m.computeIfAbsent(abbr(w), k -> new HashSet<>()).add(w);
}
}
String abbr(String w) {
return w.length() <= 2 ? w : w.charAt(0) + Integer.toString(w.length() - 2) + w.charAt(w.length() - 1);
}
public boolean isUnique(String w) {
Set b = m.getOrDefault(abbr(w), Collections.emptySet());
return b.isEmpty() || (b.size() == 1 && b.contains(w));
}
} class ValidWordAbbr {
unordered_map> m;
string abbr(const string& w) {
return w.size() <= 2 ? w : string(1, w[0]) + to_string(w.size() - 2) + w.back();
}
public:
ValidWordAbbr(vector& dict) {
unordered_set uniq(dict.begin(), dict.end());
for (auto& w : uniq) m[abbr(w)].insert(w);
}
bool isUnique(const string& w) {
auto it = m.find(abbr(w));
if (it == m.end()) return true;
return it->second.size() == 1 && it->second.count(w);
}
}; Explanation
An abbreviation squashes a word into first letter + (length of the middle) + last letter, like "deer" → "d2r". The idea is to precompute, for every distinct dictionary word, which abbreviation it maps to.
At build time we group words into a map m keyed by abbreviation, so each key points to the set of words that share it. We use the unique set of words so the same word isn't counted twice. Words of length 2 or less are their own abbreviation.
For isUnique(w), we look up w's abbreviation bucket. A word counts as unique if either the bucket is empty (no dictionary word abbreviates that way), or it contains exactly one word and that word is w itself.
Example: the dictionary gives "deer" → "d2r". Query "dear" also abbreviates to "d2r", and its bucket already holds "deer" (a different word), so the abbreviation is shared and the answer is false.