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_queueint, string>, vectorint, string>>, greaterint, 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_queueint, string>, vectorint, string>>, greaterint, string>>> generate(string target) {
        priority_queueint, string>, vectorint, string>>, greaterint, 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;
    }
};