> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/backtracking/411-minimum-unique-word-abbreviation.md).

# 411     Minimum Unique Word Abbreviation

## 411. [Minimum Unique Word Abbreviation](https://leetcode.com/problems/minimum-unique-word-abbreviation/description/)

## 1. Question

A string such as`"word"`contains the following abbreviations:

```
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
```

Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the **smallest possible** length such that it does not conflict with abbreviations of the strings in the dictionary.

Each **number** or letter in the abbreviation is considered length = 1. For example, the abbreviation "a32bc" has length = 4.

**Note:**

* In the case of multiple answers as shown in the second example below, you may return any one of them.
* Assume length of target string = **m**, and dictionary size = **n**. You may assume that **m ≤ 21**, **n ≤ 1000**, and

  **log2(n) + m ≤ 20**.

**Examples:**

```
"apple", ["blade"] -> "a4" (because "5" or "4e" conflicts with "blade")

"apple", ["plain", "amber", "blade"] -> "1p3" (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1").
```

## 2. Implementation

**(1) Recursion + Heap**

思路: 这是320和408两道题的结合体，做法是对target，我们利用320的方法，生成所有可能的abbreviations，将这些abbreviations放在一个按照长度从小到大排序的minHeap里。然后每次从minHeap取出一个abbreviation，里用408的方法查看dictionary里是否有word的abbreviation和它一样，如果有则说明当前的abbreviation有冲突，直接跳出循环，查看下一个长度的abbreviation

```java
class Solution {
    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)) {
                    noConflict = false;
                    break;
                }
            }

            if (noConflict) {
                return curAbbreviation;
            }
        }
        return "";
    }

    public void getAbbreviations(String target, int index, int count, String abbr, PriorityQueue<String> abbreviations) {
        if (index == target.length()) {
            if (count > 0) {
                abbr += count;
            }
            abbreviations.add(abbr);
            return;
        }

        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) {
        int i = 0, j = 0;
        int num = 0;

        while (i < word.length() && j < abbr.length()) {
            if (Character.isDigit(abbr.charAt(j))) {
                num = 10 * num + abbr.charAt(j) - '0';

                if (num == 0) {
                    return false;
                }
                ++j;
            }
            else {
                i += num;

                if (i >= word.length() || word.charAt(i) != abbr.charAt(j)) {
                    return false;
                }
                num = 0;
                ++i;
                ++j;
            }
        }
        i += num;

        return i == word.length() && j == abbr.length();
    }
}
```

## 3. Time & Space Complexity

**Backtracking:** 时间复杂度O(2^n + n \* 2^n + m \* n \* 2^n))

**解析:** n是target的长度, m是dictionary里word个数，时间复杂度可以分成3个部分，**第一部分**是getAbbreviations(), 需要O(2^n)。**第二部分**是while loop，我们从minHeap取出abbreviation, 每次取abbreviation需要log(2^n)的时间，总共有2^n次，所以这部分需要时间 O(n \* 2^n)。第三部分是while loop里, 对每个abbreviation, 我们对dictionary里每个word都call一次isValidAbbreviation(), dictionary有m个word，堆里总共有2^n abbreviation, 总共需要call m \* 2^n次, isValidAbbreviation需要O(n), 这部分需要O(m \* n \* 2^n)

空间复杂度O(n + 2^n), 递归深度为n，堆总共有2^n个abbreviation