LeetCode刷题实战411：最短独占单词缩写
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 最短独占单词缩写，我们先来看题面：
https://leetcode-cn.com/problems/minimum-unique-word-abbreviation/
字符串 "word" 包含以下这些缩写形式：
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
给一个目标字符串和一个字符串字典，为目标字符串找一个 最短 长度的缩写字符串，同时这个缩写字符串不是字典中其他字符串的缩写形式。
缩写形式中每一个 数字 或者字母都被视为长度为 1 。比方说，缩写形式 "a32bc" 的长度为 4 而不是 5 。
注意:
如果像第二个示例一样有多个有效答案，你可以返回它们中的任意一个。假设目标字符串的长度为 m ，字典中的字符串数目为 n 。你可以假设 m ≤ 21， n ≤ 1000， 且 log2(n) + m ≤ 20.
示例
示例1：
"apple", ["blade"] -> "a4" (因为 "5" 或者 "4e" 同时也是 "blade" 的缩写形式，所以它们是无效的缩写)
示例2：
"apple", ["plain", "amber", "blade"] -> "1p3" (其他有效的缩写形式还包括 "ap3", "a3e", "2p2", "3le", "3l1")。解题
http://t.zoukankan.com/grandyang-p-5935836.html
这道题实际上是之前那两道Valid Word Abbreviation和Generalized Abbreviation的合体，我们的思路其实很简单，首先找出target的所有的单词缩写的形式，然后按照长度来排序，小的排前面，我们用优先队列来自动排序，里面存一个pair，保存单词缩写及其长度，然后我们从最短的单词缩写开始，跟dictionary中所有的单词一一进行验证，利用Valid Word Abbreviation中的方法，看其是否是合法的单词的缩写，如果是，说明有冲突，直接break，进行下一个单词缩写的验证，参见代码如下：
class Solution {
public:
string minAbbreviation(string target, vector<string>& dictionary) {
if (dictionary.empty()) return to_string((int)target.size());
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> q;
q = generate(target);
while (!q.empty()) {
auto t = q.top(); q.pop();
bool no_conflict = true;
for (string word : dictionary) {
if (valid(word, t.second)) {
no_conflict = false;
break;
}
}
if (no_conflict) return t.second;
}
return "";
}
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> generate(string target) {
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> res;
for (int i = 0; i < pow(2, target.size()); ++i) {
string out = "";
int cnt = 0, size = 0;
for (int j = 0; j < target.size(); ++j) {
if ((i >> j) & 1) ++cnt;
else {
if (cnt != 0) {
out += to_string(cnt);
cnt = 0;
++size;
}
out += target[j];
++size;
}
}
if (cnt > 0) {
out += to_string(cnt);
++size;
}
res.push({size, out});
}
return res;
}
bool valid(string word, string abbr) {
int m = word.size(), n = abbr.size(), p = 0, cnt = 0;
for (int i = 0; i < abbr.size(); ++i) {
if (abbr[i] >= '0' && abbr[i] <= '9') {
if (cnt == 0 && abbr[i] == '0') return false;
cnt = 10 * cnt + abbr[i] - '0';
} else {
p += cnt;
if (p >= m || word[p++] != abbr[i]) return false;
cnt = 0;
}
}
return p + cnt == m;
}
};好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
腾讯云开发者
