# Leetcode 411 Solution

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

## Solution

``````class Solution {
public:
vector<string> generateAbbreviations(string word) {
vector<string> res;
res.push_back(word);

if (word.empty() == false)
{
for (int i = 0; i < word.size(); i++)
{
for (int j = i; j < word.size(); j++)
{
if (j == word.size() - 1)
res.push_back(word.substr(0, i) + to_string(j - i + 1));
else
{
auto ch = word[j + 1];
auto subres = generateAbbreviations(word.substr(j + 2));
for (auto sub : subres)
res.push_back(word.substr(0, i) + to_string(j - i + 1) + ch + sub);
}
}
}
}

return res;
}

bool validWordAbbreviation(const string& word, const string& abbr) {
int i = 0;
int j = 0;

while (i < word.size() && j < abbr.size())
{
if (isdigit(abbr[j]) == false)
{
if (word[i] != abbr[j])
return false;

i++, j++;
}
else
{
int k = j;
while (k < abbr.size() && isdigit(abbr[k]))
k++;

int len = atoi(abbr.substr(j, k - j).c_str());
if (len == 0 || to_string(len) != abbr.substr(j, k - j))
return false;

i += len;
j = k;
}
}

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

string minAbbreviation(string target, vector<string>& dictionary)
{
if (dictionary.size() == 0)

auto abbrs = generateAbbreviations(target);
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> q;

for (auto abbr : abbrs)
q.push(make_pair(abbr.size(), abbr));

while (q.empty() == false)
{
auto abbr = q.top().second;
q.pop();

bool valid = true;
for (auto word : dictionary)
if (validWordAbbreviation(word, abbr))
{
valid = false;
break;
}

if (valid)
return abbr;
}

return "";
}
};
``````