# 527 Word Abbreviation

## 527. [Word Abbreviation](https://leetcode.com/problems/word-abbreviation/description/)

## 1. Question

Given an array of n distinct non-empty strings, you need to generate **minimal** possible abbreviations for every word following rules below.

1. Begin with the first character and then the number of characters abbreviated, which followed by the last character.
2. If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words.
3. If the abbreviation doesn't make the word shorter, then keep it as original.

**Example:**

```
Input:
["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]

Output:
["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
```

**Note:**

1. Both n and the length of each word will not exceed 400.
2. The length of each word is greater than 1.
3. The words consist of lowercase English letters only.
4. The return answers should be **in the same order** as the original array.

## 2. Implementation

**(1) Trie**

思路:

```java
class Solution {
    class TrieNode {
        Word word;
        TrieNode[] childNode;

        public TrieNode() {
            childNode = new TrieNode[26];
        }
    }

    class Word {
        String word;
        int index;

        public Word(String word, int index) {
            this.word = word;
            this.index = index;
        }
    }

    public List<String> wordsAbbreviation(List<String> dict) {
        Map<String, TrieNode> map = new HashMap();
        String[] res = new String[dict.size()];

        for (int i = 0; i < dict.size(); i++) {
            String curWord = dict.get(i);
            String abbr = abbreviate(curWord, 1);

            if (!map.containsKey(abbr)) {
                TrieNode node = new TrieNode();
                node.childNode[curWord.charAt(0) - 'a'] = new TrieNode();
                node.childNode[curWord.charAt(0) - 'a'].word = new Word(curWord, i);
                map.put(abbr, node);
                res[i] = abbr;
            }
            else {
                TrieNode node = map.get(abbr);

                for (int j = 0; j < curWord.length(); j++) {
                    char c = curWord.charAt(j);

                    if (node.childNode[c - 'a'] == null) {
                        node.childNode[c - 'a'] = new TrieNode();
                        node.childNode[c - 'a'].word = new Word(curWord, i);
                        res[i] = abbreviate(curWord, j + 1);
                        break;
                    }
                    node = node.childNode[c - 'a'];

                    if (node.word != null) {
                        Word conflictWord = node.word;
                        node.word = null;
                        int k = j + 1;

                        while (conflictWord.word.charAt(k) == curWord.charAt(k)) {
                            node.childNode[curWord.charAt(k) - 'a'] = new TrieNode();
                            node = node.childNode[curWord.charAt(k) - 'a'];
                            ++k;
                        }

                        node.childNode[conflictWord.word.charAt(k) - 'a'] = new TrieNode();
                        node.childNode[conflictWord.word.charAt(k) - 'a'].word = conflictWord;
                        res[conflictWord.index] = abbreviate(conflictWord.word, k + 1);
                        node.childNode[curWord.charAt(k) - 'a'] = new TrieNode();
                        node.childNode[curWord.charAt(k) - 'a'].word = new Word(curWord, i);
                        res[i] = abbreviate(curWord, k + 1);
                        break;
                    }
                }
            }
        }
        return Arrays.asList(res);
    }

    public String abbreviate(String word, int k) {
        if (k >= word.length() - 2) {
            return word;
        }
        StringBuilder res = new StringBuilder();
        res.append(word.substring(0, k));
        res.append(word.length() - 1 - k);
        res.append(word.charAt(word.length() - 1));
        return res.toString();
    } 
}
```

**(2) Hash Set**

```java
class Solution {
    public List<String> wordsAbbreviation(List<String> dict) {
        int len = dict.size();
        int[] prefixLen = new int[len];
        String[] ans = new String[len];

        for (int i = 0; i < len; i++) {
            prefixLen[i] = 1;
            ans[i] = abbreviate(dict.get(i), 1);
        }

        for (int i = 0; i < len - 1; i++) {
            while (true) {
                Set<Integer> set = new HashSet();
                // Put the index of word in the dictionary in the hash set if their abbreviation 
                // are the same
                for (int j = i + 1; j < len; j++) {
                    if (ans[i].equals(ans[j])) {
                        set.add(j);
                    }
                }

                if (set.isEmpty()) break;

                set.add(i);

                for (int k : set) {
                    ans[k] = abbreviate(dict.get(k), ++prefixLen[k]);
                }
            }
        }
        return Arrays.asList(ans);
    }

    public String abbreviate(String word, int k) {
        if (k >= word.length() - 2) {
            return word;
        }
        StringBuilder res = new StringBuilder();
        res.append(word.substring(0, k));
        res.append(word.length() - 1 - k);
        res.append(word.charAt(word.length() - 1));
        return res.toString();
    } 
}
```

## 3. Time & Space Complexity


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/trie/527-word-abbreviation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.