Minimum Unique Word Abbreviation
Problem
Given target and a dictionary of words of the same length, find the shortest abbreviation of target that doesn't match any dictionary word.
target = "apple", dict = ["plain","amber","blade"]"1p3"def min_abbreviation(target, dictionary):
n = len(target)
diffs = []
for w in dictionary:
if len(w) != n: continue
mask = 0
for i, ch in enumerate(target):
if w[i] != ch: mask |= 1 << (n - 1 - i)
diffs.append(mask)
def abbr_len(mask):
s = 0; prev = 0; run = 0
for i in range(n):
bit = (mask >> (n - 1 - i)) & 1
if bit == 1:
if run > 0: s += 1; run = 0
s += 1
else:
run += 1
if run > 0: s += 1
return s
def abbr_str(mask):
out = []; run = 0
for i in range(n):
bit = (mask >> (n - 1 - i)) & 1
if bit == 1:
if run > 0: out.append(str(run)); run = 0
out.append(target[i])
else:
run += 1
if run > 0: out.append(str(run))
return "".join(out)
best = (n + 1, None)
for mask in range(1 << n):
if all(mask & d for d in diffs):
L = abbr_len(mask)
if L < best[0]: best = (L, mask)
return abbr_str(best[1])function minAbbreviation(target, dictionary) {
const n = target.length;
const diffs = [];
for (const w of dictionary) {
if (w.length !== n) continue;
let mask = 0;
for (let i = 0; i < n; i++) if (w[i] !== target[i]) mask |= 1 << (n - 1 - i);
diffs.push(mask);
}
function abbrLen(mask) {
let s = 0, run = 0;
for (let i = 0; i < n; i++) {
const bit = (mask >> (n - 1 - i)) & 1;
if (bit === 1) { if (run > 0) { s++; run = 0; } s++; }
else run++;
}
if (run > 0) s++;
return s;
}
function abbrStr(mask) {
let out = "", run = 0;
for (let i = 0; i < n; i++) {
const bit = (mask >> (n - 1 - i)) & 1;
if (bit === 1) { if (run > 0) { out += run; run = 0; } out += target[i]; }
else run++;
}
if (run > 0) out += run;
return out;
}
let bestLen = n + 1, bestMask = 0;
for (let mask = 0; mask < (1 << n); mask++) {
if (diffs.every(d => mask & d)) {
const L = abbrLen(mask);
if (L < bestLen) { bestLen = L; bestMask = mask; }
}
}
return abbrStr(bestMask);
}class Solution {
public String minAbbreviation(String target, String[] dictionary) {
int n = target.length();
List diffs = new ArrayList<>();
for (String w : dictionary) {
if (w.length() != n) continue;
int mask = 0;
for (int i = 0; i < n; i++) if (w.charAt(i) != target.charAt(i)) mask |= 1 << (n - 1 - i);
diffs.add(mask);
}
int bestLen = n + 1, bestMask = 0;
for (int mask = 0; mask < (1 << n); mask++) {
boolean ok = true;
for (int d : diffs) if ((mask & d) == 0) { ok = false; break; }
if (!ok) continue;
int L = abbrLen(mask, n);
if (L < bestLen) { bestLen = L; bestMask = mask; }
}
return abbrStr(bestMask, target);
}
int abbrLen(int mask, int n) {
int s = 0, run = 0;
for (int i = 0; i < n; i++) {
int bit = (mask >> (n - 1 - i)) & 1;
if (bit == 1) { if (run > 0) { s++; run = 0; } s++; }
else run++;
}
if (run > 0) s++;
return s;
}
String abbrStr(int mask, String t) {
StringBuilder out = new StringBuilder();
int run = 0, n = t.length();
for (int i = 0; i < n; i++) {
int bit = (mask >> (n - 1 - i)) & 1;
if (bit == 1) { if (run > 0) { out.append(run); run = 0; } out.append(t.charAt(i)); }
else run++;
}
if (run > 0) out.append(run);
return out.toString();
}
} class Solution {
int abbrLen(int mask, int n) {
int s = 0, run = 0;
for (int i = 0; i < n; i++) {
int bit = (mask >> (n - 1 - i)) & 1;
if (bit == 1) { if (run > 0) { s++; run = 0; } s++; }
else run++;
}
if (run > 0) s++;
return s;
}
string abbrStr(int mask, const string& t) {
string out; int run = 0, n = t.size();
for (int i = 0; i < n; i++) {
int bit = (mask >> (n - 1 - i)) & 1;
if (bit == 1) { if (run > 0) { out += to_string(run); run = 0; } out += t[i]; }
else run++;
}
if (run > 0) out += to_string(run);
return out;
}
public:
string minAbbreviation(string target, vector& dictionary) {
int n = target.size();
vector diffs;
for (auto& w : dictionary) {
if ((int)w.size() != n) continue;
int mask = 0;
for (int i = 0; i < n; i++) if (w[i] != target[i]) mask |= 1 << (n - 1 - i);
diffs.push_back(mask);
}
int bestLen = n + 1, bestMask = 0;
for (int mask = 0; mask < (1 << n); mask++) {
bool ok = true;
for (int d : diffs) if (!(mask & d)) { ok = false; break; }
if (!ok) continue;
int L = abbrLen(mask, n);
if (L < bestLen) { bestLen = L; bestMask = mask; }
}
return abbrStr(bestMask, target);
}
}; Explanation
An abbreviation keeps some letters of target and replaces runs of the rest with numbers (like "1p3"). We can describe any abbreviation by a bitmask: bit on means "keep this position," bit off means "collapse it into a number." We want the shortest abbreviation that no dictionary word matches.
The key insight is precomputing a diff mask for each dictionary word: bit i is set wherever that word's letter differs from target. To beat a dictionary word, our kept positions must include at least one place they disagree — which is exactly the test mask & diff != 0.
So we loop over all 2^n keep-masks. A mask is valid only if mask & d is non-zero for every diff d, meaning it distinguishes the target from each dictionary word. Among valid masks we pick the one whose abbreviation is shortest using abbrLen.
Example: target = "apple", dict words differ from it in various spots. Keeping just the second p distinguishes all of them, and that produces the abbreviation "1p3" of length 3.
Finally abbrStr turns the winning mask into text by writing kept letters and counting the collapsed runs as numbers.