public String minAbbreviation(String target, String[] dictionary) {
if (dictionary == null || dictionary.length == 0) {
return String.valueOf(target.length());
PriorityQueue<String> abbreviations = new PriorityQueue<>((a, b)->(a.length() - b.length()));
getAbbreviations(target, 0, 0, "", abbreviations);
while (!abbreviations.isEmpty()) {
String curAbbreviation = abbreviations.remove();
boolean noConflict = true;
for (String word : dictionary) {
if (isValidAbbreviation(word, curAbbreviation)) {
public void getAbbreviations(String target, int index, int count, String abbr, PriorityQueue<String> abbreviations) {
if (index == target.length()) {
getAbbreviations(target, index + 1, count + 1, abbr, abbreviations);
getAbbreviations(target, index + 1, 0, abbr + (count == 0 ? "" : count) + target.charAt(index), abbreviations);
public boolean isValidAbbreviation(String word, String abbr) {
while (i < word.length() && j < abbr.length()) {
if (Character.isDigit(abbr.charAt(j))) {
num = 10 * num + abbr.charAt(j) - '0';
if (i >= word.length() || word.charAt(i) != abbr.charAt(j)) {
return i == word.length() && j == abbr.length();