Problem Explanation

Given a target string and a set of strings in a dictionary, you are to find an abbreviation of this target string with the smallest possible length such that it doesn't conflict with abbreviations of the strings in the dictionary.

It is important to note that each number or letter in the abbreviation is considered length = 1.

For example, given target = "apple" and dictionary = ["blade"], the result would be "a4" because "5" or "4e" might conflict with "blade".

Approach

The approach is to generate all possible abbreviations of a given target string and then check these against the dictionary to find the abbreviation that does not conflict with any of the words in the dictionary. If there are multiple possible abbreviations with the same shortest length, any of them can be returned.

The way to generate all possible abbreviations is by iterating through all the bitmasks of the length of the string. Each bit in the bitmask represents whether the corresponding character in the string is replaced by a number (1) or remained as is (0). When we find a candidate abbreviation, it means that this abbreviation does not conflict with any of the words in the dictionary. We then store it in a list of possible abbreviations.

After generating all possible abbreviations, we go through this list, calculate their length and return the one with the smallest possible length.

Let's see through examples how it works.

Consider target = "apple" and dictionary = ["blade"]. The target word "apple" can be abbreviated as ["5", "4e", "a4"....]. And the dictionary word "blade" can be abbreviated as ["5", "4e", "b4"....]. It can be seen that "5" or "4e" is conflict with "blade" because they're both valid abbreviations for "apple" and "blade". We then need to find a valid abbreviation for "apple" that does not conflict with any of the abbreviations for "blade", return it with the smallest possible length which is "a4".

Solution

C++

1
2cpp
3class Solution {
4public:
5    string minAbbreviation(string target, vector<string>& dictionary) {
6        const int m = target.length();
7        vector<int> masks;
8        for (const string& word : dictionary) {
9            if (word.length() != m)
10                continue;
11            // Compute each valid word's mask
12            masks.push_back(getMask(target, word));
13        }
14        // If there's no word with the same length, simply return the length
15        if (masks.empty())
16            return to_string(m);
17        // Compute all the abbreviations
18        vector<string> abbrs;
19        const int maxCand = pow(2, m);
20        for (int cand = 0; cand < maxCand; ++cand)
21            if (all_of(begin(masks), end(masks),  [cand](int mask) { return cand & mask; }))
22                abbrs.push_back(getAbbr(target, cand));
23        string ans = target;
24        // Among all the abbreviations find the smallest one
25        for (const string& abbr : abbrs)
26            if (getAbbrLen(abbr) < getAbbrLen(ans))
27                ans = abbr;
28        return ans;
29    }
30
31private:
32    int getMask(const string& target, const string& word) {
33        const int m = target.length();
34        // If two characters at the same position are the same, the mask bit is 0
35        // Otherwise, the mask bit is 1
36        int mask = 0;
37        for (int i = 0; i < m; ++i)
38            if (word[i] != target[i])
39                mask |= 1 << m - 1 - i;
40        return mask;
41    }
42
43    // Convert the candidate to the abbreviation
44    string getAbbr(const string& target, int cand) {
45        const int m = target.length();
46        string abbr;
47        int replacedCount = 0;
48        for (int i = 0; i < m; ++i)
49            if (cand >> m - 1 - i & 1) {
50                if (replacedCount > 0)
51                    abbr += to_string(replacedCount);
52                abbr += target[i];
53                replacedCount = 0;
54            } else {
55                ++replacedCount;
56            }
57        if (replacedCount > 0)
58            abbr += to_string(replacedCount);
59        return abbr;
60    }
61
62    int getAbbrLen(const string& abbr) {
63        int abbrLen = 0;
64        int i = 0, j = 0;
65        while (i < abbr.length()) {
66            if (isalpha(abbr[j]))
67                ++j;
68            else
69                while (j < abbr.length() && isdigit(abbr[j]))
70                    ++j;
71            ++abbrLen;
72            i = j;
73        }
74        return abbrLen;
75    }
76};

Unfortunately the solution code provided for this problem does not include solutions in Python, JavaScript, Java and C#. The algorithms used in the solution are quite advanced and could take a considerable amount of time to converted to each programming language.## Python

Here's how you might implement this algorithm in Python:

1
2python
3class Solution:
4    def minAbbreviation(self, target, dictionary):
5        def mask(word1, word2):
6            """Calculate a bitmask for two words of same length"""
7            word_len = len(word1)
8            msk = 0
9            for i in range(word_len):
10                if word1[i] != word2[i]:
11                    msk |= 1 << word_len - 1 - i
12            return msk
13
14        def to_abbr(target, cand):
15            """Convert a candidate bitmask to an abbreviation"""
16            word_len = len(target)
17            abbr = ''
18            count = 0
19            for i in range(word_len):
20                if cand >> word_len - 1 - i & 1:
21                    if count > 0:
22                        abbr += str(count)
23                    abbr += target[i]
24                    count = 0
25                else:
26                    count += 1
27            if count > 0:
28                abbr += str(count)
29            return abbr
30
31        def abbr_length(abbr):
32            """Calculate the length of an abbreviation"""
33            abbr_len = 0
34            i = 0
35            while i < len(abbr):
36                if abbr[i].isalpha():
37                    i += 1
38                else:
39                    while i < len(abbr) and abbr[i].isdigit():
40                        i += 1
41                abbr_len += 1
42            return abbr_len
43        
44        m = len(target)
45        masks = [mask(target, word) for word in dictionary if len(word) == m]
46
47        if not masks:
48            return str(m)
49
50        abbrs = []
51        max_cand = 2 ** m
52        for cand in range(max_cand):
53            if all(cand & msk for msk in masks):
54                abbrs.append(to_abbr(target, cand))
55
56        shortest = target
57        for abbr in abbrs:
58            if abbr_length(abbr) < abbr_length(shortest):
59                shortest = abbr
60
61        return shortest

Solution Implementation