夜夜撸av,黄色成人视频免费观看,国产小骚逼,九九九亚洲视频,三级av一区,一级免费片,伊人网在线观看,麻酥酥在线视频

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從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的所有的單詞縮寫的形式，然后按照長度來排序，小的排前面，我們用優(yōu)先隊列來自動排序，里面存一個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;
????}
};