Given a target string and a dictionary of strings of the same length, your goal is to find the minimum-length abbreviation of target such that it does not conflict with any word in the dictionary.
An abbreviation replaces consecutive letters with their count (e.g., "apple" can be abbreviated as "a3e", "2p2", "5", etc.). An abbreviation conflicts with a word if it can also represent that word (i.e., the abbreviation matches that word's letters/positions).
target.
At first glance, we might think to generate all possible abbreviations of target and check which ones don't conflict with any dictionary word. However, the number of abbreviations grows exponentially with the string length, making brute-force infeasible.
To optimize, we realize that:
target from dictionary words at positions where they differ.target unique among the dictionary.The solution leverages bit manipulation and BFS/DFS to efficiently search for the minimum unique abbreviation:
target and the word differ.target.n (where n is the length of target).target (i.e., bitmask & diff_mask != 0).target.
Input:
target = "apple"
dictionary = ["blade"]
target and every dictionary word.
The Minimum Unique Word Abbreviation problem can be solved efficiently by representing abbreviations as bitmasks and using bitwise operations to quickly check for conflicts with the dictionary. By focusing on positions where target and dictionary words differ, and searching for the abbreviation that keeps the fewest letters while remaining unique, we find the minimal abbreviation without brute-forcing all possibilities. This approach is elegant, efficient, and demonstrates the power of bit manipulation in string problems.
class Solution:
def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
n = len(target)
diffs = []
for word in dictionary:
if len(word) != n:
continue
diff = 0
for i in range(n):
if target[i] != word[i]:
diff |= 1 << i
diffs.append(diff)
if not diffs:
return str(n)
def abbr_len(mask):
count = 0
i = 0
while i < n:
if not (mask & (1 << i)):
while i < n and not (mask & (1 << i)):
i += 1
count += 1
else:
i += 1
count += 1
return count
res_mask = None
res_len = n + 1
for mask in range(1 << n):
valid = True
for diff in diffs:
if (mask & diff) == 0:
valid = False
break
if valid:
length = abbr_len(mask)
if length < res_len:
res_len = length
res_mask = mask
def to_abbr(mask):
res = []
i = 0
while i < n:
if not (mask & (1 << i)):
cnt = 0
while i < n and not (mask & (1 << i)):
i += 1
cnt += 1
res.append(str(cnt))
else:
res.append(target[i])
i += 1
return ''.join(res)
return to_abbr(res_mask)
class Solution {
public:
string minAbbreviation(string target, vector<string>& dictionary) {
int n = target.size();
vector<int> diffs;
for (const string& word : dictionary) {
if (word.size() != n) continue;
int diff = 0;
for (int i = 0; i < n; ++i)
if (target[i] != word[i])
diff |= (1 << i);
diffs.push_back(diff);
}
if (diffs.empty()) return to_string(n);
int resMask = 0, resLen = n + 1;
for (int mask = 0; mask < (1 << n); ++mask) {
bool valid = true;
for (int diff : diffs)
if ((mask & diff) == 0) {
valid = false;
break;
}
if (valid) {
int len = abbrLen(mask, n);
if (len < resLen) {
resLen = len;
resMask = mask;
}
}
}
return toAbbr(target, resMask);
}
int abbrLen(int mask, int n) {
int count = 0, i = 0;
while (i < n) {
if (!(mask & (1 << i))) {
while (i < n && !(mask & (1 << i))) ++i;
++count;
} else {
++i;
++count;
}
}
return count;
}
string toAbbr(const string& target, int mask) {
int n = target.size();
string res;
int i = 0;
while (i < n) {
if (!(mask & (1 << i))) {
int cnt = 0;
while (i < n && !(mask & (1 << i))) {
++i; ++cnt;
}
res += to_string(cnt);
} else {
res += target[i++];
}
}
return res;
}
};
class Solution {
public String minAbbreviation(String target, String[] dictionary) {
int n = target.length();
List<Integer> diffs = new ArrayList<>();
for (String word : dictionary) {
if (word.length() != n) continue;
int diff = 0;
for (int i = 0; i < n; ++i)
if (target.charAt(i) != word.charAt(i))
diff |= (1 << i);
diffs.add(diff);
}
if (diffs.isEmpty()) return String.valueOf(n);
int resMask = 0, resLen = n + 1;
for (int mask = 0; mask < (1 << n); ++mask) {
boolean valid = true;
for (int diff : diffs)
if ((mask & diff) == 0) {
valid = false;
break;
}
if (valid) {
int len = abbrLen(mask, n);
if (len < resLen) {
resLen = len;
resMask = mask;
}
}
}
return toAbbr(target, resMask);
}
private int abbrLen(int mask, int n) {
int count = 0, i = 0;
while (i < n) {
if ((mask & (1 << i)) == 0) {
while (i < n && (mask & (1 << i)) == 0) ++i;
++count;
} else {
++i;
++count;
}
}
return count;
}
private String toAbbr(String target, int mask) {
int n = target.length();
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < n) {
if ((mask & (1 << i)) == 0) {
int cnt = 0;
while (i < n && (mask & (1 << i)) == 0) {
++i; ++cnt;
}
sb.append(cnt);
} else {
sb.append(target.charAt(i++));
}
}
return sb.toString();
}
}
var minAbbreviation = function(target, dictionary) {
const n = target.length;
let diffs = [];
for (let word of dictionary) {
if (word.length !== n) continue;
let diff = 0;
for (let i = 0; i < n; ++i) {
if (target[i] !== word[i]) {
diff |= (1 << i);
}
}
diffs.push(diff);
}
if (diffs.length === 0) return n.toString();
function abbrLen(mask) {
let count = 0, i = 0;
while (i < n) {
if (!(mask & (1 << i))) {
while (i < n && !(mask & (1 << i))) ++i;
++count;
} else {
++i;
++count;
}
}
return count;
}
let resMask = null, resLen = n + 1;
for (let mask = 0; mask < (1 << n); ++mask) {
let valid = true;
for (let diff of diffs) {
if ((mask & diff) === 0) {
valid = false;
break;
}
}
if (valid) {
let length = abbrLen(mask);
if (length < resLen) {
resLen = length;
resMask = mask;
}
}
}
function toAbbr(mask) {
let res = [];
let i = 0;
while (i < n) {
if (!(mask & (1 << i))) {
let cnt = 0;
while (i < n && !(mask & (1 << i))) {
++i; ++cnt;
}
res.push(cnt);
} else {
res.push(target[i]);
++i;
}
}
return res.join('');
}
return toAbbr(resMask);
};