The "Word Abbreviation" problem asks you to generate the minimal unique abbreviation for each word in a given list of words. An abbreviation for a word is constructed by keeping its first letter, then a number representing how many characters are omitted in the middle, and finally the last letter. For example, the word localization can be abbreviated as l10n (the 10 represents the 10 letters omitted between 'l' and 'n').
However, if two or more words share the same abbreviation, you must increase the prefix length (i.e., include more starting characters before the number) until every abbreviation in the list is unique. The abbreviation must be as short as possible while ensuring uniqueness within the list.
Constraints:
At first glance, the problem seems straightforward: abbreviate every word using the first letter, the count of omitted letters, and the last letter. However, conflicts arise when two or more words have the same abbreviation. The naive approach would be to generate abbreviations and check for duplicates, but this can become inefficient, especially for large word lists.
To optimize, we need a way to systematically resolve conflicts by gradually increasing the prefix length until all abbreviations are unique. This suggests a grouping strategy: for each set of words sharing an abbreviation, we increase the prefix for just those words, repeating as necessary.
Analogously, it's like giving people nicknames in a group: if two people have the same nickname, you add more of their first name until everyone is uniquely identified.
Let's break down the solution step by step:
Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
Brute-force approach:
The optimized approach is much faster in practice, especially for large, diverse word lists.
To solve the Word Abbreviation problem, we iteratively generate the shortest possible abbreviation for each word, resolving conflicts by increasing the prefix length only where necessary. This strategy ensures all abbreviations are unique and as concise as possible. Using hash maps for grouping and conflict resolution provides efficient lookups and updates, making the solution both elegant and performant. The approach balances clarity and efficiency, and can be adapted to similar problems involving minimal unique representations.
from collections import defaultdict
def abbreviate(word, prefix_len):
if len(word) <= 3:
return word
if prefix_len >= len(word) - 2:
return word
num = len(word) - prefix_len - 1
return word[:prefix_len] + str(num) + word[-1]
def wordsAbbreviation(words):
n = len(words)
prefix_lens = [1] * n
result = [None] * n
while True:
abbr_dict = defaultdict(list)
for i, word in enumerate(words):
abbr = abbreviate(word, prefix_lens[i])
result[i] = abbr
abbr_dict[abbr].append(i)
unique = True
for abbr, idxs in abbr_dict.items():
if len(idxs) > 1:
unique = False
for idx in idxs:
prefix_lens[idx] += 1
if unique:
break
return result
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
string abbreviate(const string& word, int prefix_len) {
if (word.size() <= 3) return word;
if (prefix_len >= word.size() - 2) return word;
int num = word.size() - prefix_len - 1;
return word.substr(0, prefix_len) + to_string(num) + word.back();
}
vector<string> wordsAbbreviation(vector<string>& words) {
int n = words.size();
vector<int> prefix_lens(n, 1);
vector<string> result(n);
while (true) {
unordered_map<string, vector<int>> abbr_dict;
for (int i = 0; i < n; ++i) {
string abbr = abbreviate(words[i], prefix_lens[i]);
result[i] = abbr;
abbr_dict[abbr].push_back(i);
}
bool unique = true;
for (auto& p : abbr_dict) {
if (p.second.size() > 1) {
unique = false;
for (int idx : p.second) {
prefix_lens[idx]++;
}
}
}
if (unique) break;
}
return result;
}
import java.util.*;
public class Solution {
private String abbreviate(String word, int prefixLen) {
if (word.length() <= 3) return word;
if (prefixLen >= word.length() - 2) return word;
int num = word.length() - prefixLen - 1;
return word.substring(0, prefixLen) + num + word.charAt(word.length() - 1);
}
public List<String> wordsAbbreviation(List<String> words) {
int n = words.size();
int[] prefixLens = new int[n];
Arrays.fill(prefixLens, 1);
String[] result = new String[n];
while (true) {
Map<String, List<Integer>> abbrDict = new HashMap<>();
for (int i = 0; i < n; i++) {
String abbr = abbreviate(words.get(i), prefixLens[i]);
result[i] = abbr;
abbrDict.computeIfAbsent(abbr, k -> new ArrayList<>()).add(i);
}
boolean unique = true;
for (List<Integer> idxs : abbrDict.values()) {
if (idxs.size() > 1) {
unique = false;
for (int idx : idxs) {
prefixLens[idx]++;
}
}
}
if (unique) break;
}
return Arrays.asList(result);
}
}
function abbreviate(word, prefixLen) {
if (word.length <= 3) return word;
if (prefixLen >= word.length - 2) return word;
let num = word.length - prefixLen - 1;
return word.slice(0, prefixLen) + num + word[word.length - 1];
}
function wordsAbbreviation(words) {
const n = words.length;
const prefixLens = Array(n).fill(1);
const result = Array(n);
while (true) {
const abbrDict = {};
for (let i = 0; i < n; i++) {
const abbr = abbreviate(words[i], prefixLens[i]);
result[i] = abbr;
if (!abbrDict[abbr]) abbrDict[abbr] = [];
abbrDict[abbr].push(i);
}
let unique = true;
for (const abbr in abbrDict) {
if (abbrDict[abbr].length > 1) {
unique = false;
for (const idx of abbrDict[abbr]) {
prefixLens[idx]++;
}
}
}
if (unique) break;
}
return result;
}