The idea is naive, just as mentioned in other posts, it's fast maybe because we used bit manipulation here, we do the following to solve this problem:

- Since only strings with the same length as the target would possible have the same abbreviation, we create a diff-number for those strings in the dictionary, with
`0`

represents same character, `1`

represents different character.
- We use backtrack to generate all possible abbreviation for the target, with
`1`

means that we will keep the char in the result, `0`

means that we will abbreviate it.
- For these abbreviations, we check if it won't conflict with any strings in the dictionary, with
`res`

represents the abbreviation of the target, `n`

represents the diff-number in the set, if `(res & n) != 0`

, we know that there is at least one char that is in the abbreviation but not in the words in the dictionary, thus this is a valid abbreviation.
- After we check all the possible abbreviations, we convert the result abbreviation number to the actual abbreviation string, we get an answer.

Below is my code.

```
public class Solution {
private int minL;//Min length of the result
private int result;//Result int
private Set<Integer> set;
public String minAbbreviation(String target, String[] dictionary) {
set = new HashSet<>();
for(String s : dictionary)//Generate diff-numbers
{
if(s.length() == target.length())
{
set.add(getBitMask(s, target));
}
}
if(set.size() == 0) return target.length() + "";//return if all words are of different length
minL = target.length() + 1;
result = -1;
//generate all possible abbreviation
backTrack(0, target.length(), 0, 0);
//Construct result string using result int
int number = 0;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < target.length(); i++)
{
if(((result >> (target.length() - i - 1)) & 1) == 1)
{
sb.append(number > 0 ? number : "").append(target.charAt(i));
number = 0;
}
else number++;
}
return sb.append(number > 0 ? number : "").toString();
}
//curL is to keep track of the length of current abbreviation
public void backTrack(int cur, int l, int res, int curL)
{
if(cur == l)
{
if(curL < minL)
{
for(int n : set)//check whether the abbr is valid
{
if((res & n) == 0) return;
}
minL = curL;
result = res;
}
}
else
{
if((res & 1) == 1 || cur == 0) backTrack(cur + 1, l, res << 1, curL + 1);
else backTrack(cur + 1, l, res << 1, curL);
backTrack(cur + 1, l, (res << 1) + 1, curL + 1);
}
}
public int getBitMask(String s, String t)
{
int mask = 0;
for(int i = 0; i < s.length(); i++)
{
mask = mask << 1;
if(s.charAt(i) != t.charAt(i)) mask += 1;
}
return mask;
}
}
```