# 527. Word Abbreviation

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.

``````class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& dict) {
int n = dict.size();
vector<string> res(n);
vector<int> pre(n, 1);
for (int i = 0; i < n; ++i) {
res[i] = abbreviate(dict[i], pre[i]);
}
for (int i = 0; i < n; ++i) {
while (true) {
unordered_set<int> st;
for (int j = i + 1; j < n; ++j) {
if (res[j] == res[i]) st.insert(j);
}
if (st.empty()) break;
st.insert(i);
for (auto a : st) {
res[a] = abbreviate(dict[a], ++pre[a]);
}
}
}
return res;
}
string abbreviate(string s, int k) {
return (k >= (int)s.size() - 2) ? s : s.substr(0, k) + to_string((int)s.size() - k - 1) + s.back();
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/527

Minimum Unique Word Abbreviation

Valid Word Abbreviation

Generalized Abbreviation

Unique Word Abbreviation

https://leetcode.com/problems/word-abbreviation/

https://leetcode.com/problems/word-abbreviation/discuss/99792/HashMap-%2B-Trie-greater-O(nL)-solution

https://leetcode.com/problems/word-abbreviation/discuss/99782/Really-simple-and-straightforward-Java-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation