## Minimum Unique Word Abbreviation

• Time:O(2^m \cdot nm)
• Space:O(2^m \cdot m)

## C++

class Solution {
public:
string minAbbreviation(string target, vector<string>& dictionary) {
const int m = target.length();

for (const auto& word : dictionary) {
if (word.length() != m)
continue;
}

vector<string> abbrs;

const int maxCand = pow(2, m);
// for all candidate representation of target
for (int cand = 0; cand < maxCand; ++cand)
// all masks have at lease one bit different from candidate
[cand](int mask) { return cand & mask; }))
abbrs.push_back(getAbbr(target, cand));

string ans = target;

for (const auto& abbr : abbrs)
if (getAbbrLen(abbr) < getAbbrLen(ans))
ans = abbr;

return ans;
}

private:
int getMask(const string& target, const string& word) {
const int m = target.length();
// mask[i] = 0 := target[i] == word[i]
// mask[i] = 1 := target[i] != word[i]
// e.g. target = "apple"
//        word = "blade"
//        mask =  11110
int mask = 0;
for (int i = 0; i < m; ++i)
if (word[i] != target[i])
mask |= 1 << m - 1 - i;
}

string getAbbr(const string& target, int cand) {
const int m = target.length();
string abbr;
int replacedCount = 0;
for (int i = 0; i < m; ++i)
if (cand >> m - 1 - i & 1) {
// cand[i] = 1, abbr should show the original character
if (replacedCount)
abbr += to_string(replacedCount);
abbr += target[i];
replacedCount = 0;
} else {
// cand[i] = 0, abbr can be replaced
++replacedCount;
}
if (replacedCount)
abbr += to_string(replacedCount);
return abbr;
}

int getAbbrLen(const string& abbr) {
int abbrLen = 0;
int i = 0;
int j = 0;
while (i < abbr.length()) {
if (isalpha(abbr[j]))
++j;
else
while (j < abbr.length() && isdigit(abbr[j]))
++j;
++abbrLen;
i = j;
}
return abbrLen;
}
};


## JAVA

class Solution {
public String minAbbreviation(String target, String[] dictionary) {
final int m = target.length();
List<Integer> masks = new ArrayList<>();

for (final String word : dictionary) {
if (word.length() != m)
continue;
}

return String.valueOf(m);

List<String> abbrs = new ArrayList<>();

final int maxCand = (int) Math.pow(2, m);
// for all candidate representation of target
for (int i = 0; i < maxCand; ++i) {
final int cand = i;
// all masks have at lease one bit different from candidate
}

String ans = target;

for (final String abbr : abbrs)
if (getAbbrLen(abbr) < getAbbrLen(ans))
ans = abbr;

return ans;
}

private int getMask(final String target, final String word) {
final int m = target.length();
// mask[i] = 0 := target[i] == word[i]
// mask[i] = 1 := target[i] != word[i]
// e.g. target = "apple"
//        word = "blade"
//        mask =  11110
int mask = 0;
for (int i = 0; i < m; ++i)
if (word.charAt(i) != target.charAt(i))
mask |= 1 << m - 1 - i;
}

String getAbbr(final String target, int cand) {
final int m = target.length();
StringBuilder sb = new StringBuilder();
int replacedCount = 0;
for (int i = 0; i < m; ++i)
if ((cand >> m - 1 - i & 1) == 1) {
// cand[i] = 1, abbr should show the original character
if (replacedCount > 0)
sb.append(replacedCount);
sb.append(target.charAt(i));
replacedCount = 0;
} else {
// cand[i] = 0, abbr can be replaced
++replacedCount;
}
if (replacedCount > 0)
sb.append(replacedCount);
return sb.toString();
}

int getAbbrLen(final String abbr) {
int abbrLen = 0;
int i = 0;
int j = 0;
while (i < abbr.length()) {
if (Character.isAlphabetic(abbr.charAt(j)))
++j;
else
while (j < abbr.length() && Character.isDigit(abbr.charAt(j)))
++j;
++abbrLen;
i = j;
}
return abbrLen;
}
}


## Python

class Solution:
def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
m = len(target)

def getMask(word: str) -> int:
# mask[i] = 0 := target[i] == word[i]
# mask[i] = 1 := target[i] != word[i]
# e.g. target = "apple"
#        word = "blade"
#        mask =  11110
for i, c in enumerate(word):
if c != target[i]:
mask |= 1 << m - 1 - i

masks = [getMask(word) for word in dictionary if len(word) == m]
return str(m)

abbrs = []

def getAbbr(cand: int) -> str:
abbr = ''
replacedCount = 0
for i, c in enumerate(target):
if cand >> m - 1 - i & 1:
# cand[i] = 1, abbr should show the original character
if replacedCount:
abbr += str(replacedCount)
abbr += c
replacedCount = 0
else:
# cand[i] = 0, abbr can be replaced
replacedCount += 1
if replacedCount:
abbr += str(replacedCount)
return abbr

# for all candidate representation of target
for cand in range(2**m):
# all masks have at lease one bit different from candidate
abbr = getAbbr(cand)
abbrs.append(abbr)

def getAbbrLen(abbr: str) -> int:
abbrLen = 0
i = 0
j = 0
while i < len(abbr):
if abbr[j].isalpha():
j += 1
else:
while j < len(abbr) and abbr[j].isdigit():
j += 1
abbrLen += 1
i = j
return abbrLen

return min(abbrs, key=lambda x: getAbbrLen(x))